可以做投票的网站,上海贸易公司注册条件,南昌做网站需要多少钱,爱南宁app下载官网最新版题目描述
某工程师为了解决服务器负载过高的问题#xff0c;决定使用多个服务器来分担请求消息。 现给定 k 台服务器#xff08;编号从 1 到 k#xff09;#xff0c;以及一批请求消息的信息#xff0c;格式为到达时刻 负载大小#xff0c;消息说明#xff1a; 每个时刻…题目描述
某工程师为了解决服务器负载过高的问题决定使用多个服务器来分担请求消息。 现给定 k 台服务器编号从 1 到 k以及一批请求消息的信息格式为到达时刻 负载大小消息说明 每个时刻最多只有一条消息到达 负载大小表示服务器处理该消息所需时长。 请计算在负载分担规则下哪些服务器处理的负载最高服务器处理的负载为所处理的所有消息的负载累加和并以升序返回这些服务器的编号。 负载分担规则 按顺序循环分配服务器如有3台服务器且都空闲分配的方式为 1-2-3-1… 如果某台服务器繁忙则跳过该服务器 如果一条消息到达时所有服务器繁忙则丢弃这条消息。
解答要求
时间限制1000ms, 内存限制512MB 输入 第一行为服务器的个数 kk 的范围 [1, 50000] 第二行为请求消息个数 nn 的范围 [1, 50000] 随后的 n 行为各条消息的到达时刻和负载大小注意并非按到达时刻升序给出。 消息到达时刻的范围 [1, 10^9]负载大小的范围 [1, 10^9]
输出
处理负载最多的服务器编号注意按升序输出。
样例
输入样例 1
3
7
1 15
2 10
12 10
5 10
6 10
30 15
32 10输出样例 1
1 3提示样例 1
根据输入信息经过分析可得以下表
到达时刻消息负载完成时刻不包含分配服务器号11516121012251015361016丢弃121022230154533210421
根据上表分析1和3号服务器处理的负载都为25按照升序排列输出的结果为:1 3
Java算法源码
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;public class Main {// 待实现函数在此函数中填入答题代码static int[] findHighestLoadServers(int serverNum, Message[] messages) {boolean[] isBusy new boolean[serverNum]; // 下标为server编号-1值为是否忙碌int[] serverLoad new int[serverNum]; // 下标为server编号-1值为总LoadMessage[] processingMsg new Message[serverNum]; // 下标为server编号-1值为目前仍在处理的 message信息// 首先将消息按时间排序Arrays.sort(messages, Comparator.comparingInt(o - o.time));int lastProcessIdx -1; // 上次分配执行的服务器从-1开始// 依次处理 messagesfor (Message message : messages) {// 首先更新时间updateTime(message.time, isBusy, processingMsg, serverNum);// 从 lastProcessIdx 下一个位置开始循环找到第一个空闲的server// 按顺序循环分配服务器i最大值可为 2 * serverNum使用 i % serverNum 得到对应循环的下标for (int i lastProcessIdx 1; i 2 * serverNum; i) {// 不忙说明找到空闲的Serverif (!isBusy[i % serverNum]) {processingMsg[i % serverNum] message; // message添加到processingMsgserverLoad[i % serverNum] message.load; // 计算该server的总负载值isBusy[i % serverNum] true; // 标记该server为忙碌lastProcessIdx i % serverNum; // 记录下 lastProcessIdx 以下次循环使用break;}}}// 统计结果Listint[] idLoadArrList new ArrayList(); // [serverId, serverLoad]for (int i 0; i serverNum; i) {idLoadArrList.add(new int[] {i 1, serverLoad[i]});}idLoadArrList.sort((o1, o2) - o1[1] ! o2[1] ? o2[1] - o1[1] : o1[0] - o2[0]); // 按serverLoad降序serverId升序// 生成答案ListInteger ansList new ArrayList();ansList.add(idLoadArrList.get(0)[0]);int maxLoad idLoadArrList.get(0)[1];int i 1;// 将与最大值相等的serverId加入结果集while (i idLoadArrList.size() idLoadArrList.get(i)[1] maxLoad) {ansList.add(idLoadArrList.get(i)[0]);i;}return ansList.stream().mapToInt(Integer::valueOf).toArray();}private static void updateTime(int time, boolean[] isBusy, Message[] processingMsg, int serverNum) {for (int i 0; i serverNum; i) {// 空闲的不处理if (!isBusy[i]) {continue;}// 忙碌的检查是否处理完了Message message processingMsg[i];if (message.time message.load time) {isBusy[i] false;processingMsg[i] null;}}}static class Message {int time;int load;};public static void main(String[] args) {Scanner cin new Scanner(System.in, StandardCharsets.UTF_8.name());int serverNum cin.nextInt();int messageNum cin.nextInt();Message[] messages new Message[messageNum];for (int i 0; i messages.length; i) {Message message new Message();message.time cin.nextInt();message.load cin.nextInt();messages[i] message;}cin.close();int[] highestLoadServers findHighestLoadServers(serverNum, messages);String[] strResult Arrays.stream(highestLoadServers).mapToObj(String::valueOf).toArray(String[]::new);System.out.println(String.join( , strResult));}
}
