題目描述

某工程師為了解決服務(wù)器負(fù)載過(guò)高的問(wèn)題，決定使用多個(gè)服務(wù)器來(lái)分擔(dān)請(qǐng)求消息。
現(xiàn)給定 k 臺(tái)服務(wù)器（編號(hào)從 1 到 k），以及一批請(qǐng)求消息的信息，格式為到達(dá)時(shí)刻 負(fù)載大小，消息說(shuō)明：
每個(gè)時(shí)刻最多只有一條消息到達(dá)；
負(fù)載大小表示服務(wù)器處理該消息所需時(shí)長(zhǎng)。
請(qǐng)計(jì)算在負(fù)載分擔(dān)規(guī)則下，哪些服務(wù)器處理的負(fù)載最高（服務(wù)器處理的負(fù)載為所處理的所有消息的負(fù)載累加和），并以升序返回這些服務(wù)器的編號(hào)。
負(fù)載分擔(dān)規(guī)則：
按順序循環(huán)分配服務(wù)器，如：有3臺(tái)服務(wù)器且都空閑，分配的方式為 1->2->3->1… ；
如果某臺(tái)服務(wù)器繁忙，則跳過(guò)該服務(wù)器；
如果一條消息到達(dá)時(shí)所有服務(wù)器繁忙，則丟棄這條消息。

解答要求

時(shí)間限制：1000ms, 內(nèi)存限制：512MB
輸入
第一行為服務(wù)器的個(gè)數(shù) k，k 的范圍 [1, 50000]
第二行為請(qǐng)求消息個(gè)數(shù) n，n 的范圍 [1, 50000]
隨后的 n 行為各條消息的到達(dá)時(shí)刻和負(fù)載大小（注意并非按到達(dá)時(shí)刻升序給出）。
消息到達(dá)時(shí)刻的范圍 [1, 10^9]，負(fù)載大小的范圍 [1, 10^9]

輸出

處理負(fù)載最多的服務(wù)器編號(hào)，注意按升序輸出。

樣例

輸入樣例 1

3
7
1 15
2 10
12 10
5 10
6 10
30 15
32 10

輸出樣例 1

1 3

提示樣例 1

根據(jù)輸入信息，經(jīng)過(guò)分析可得以下表：

到達(dá)時(shí)刻	消息負(fù)載	完成時(shí)刻（不包含）	分配服務(wù)器號(hào)
1	15	16	1
2	10	12	2
5	10	15	3
6	10	16	丟棄
12	10	22	2
30	15	45	3
32	10	42	1

根據(jù)上表分析，1和3號(hào)服務(wù)器處理的負(fù)載都為25，按照升序排列，輸出的結(jié)果為: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 {// 待實(shí)現(xiàn)函數(shù)，在此函數(shù)中填入答題代碼static int[] findHighestLoadServers(int serverNum, Message[] messages) {boolean[] isBusy = new boolean[serverNum]; // 下標(biāo)為server編號(hào)-1，值為是否忙碌int[] serverLoad = new int[serverNum]; // 下標(biāo)為server編號(hào)-1，值為總LoadMessage[] processingMsg = new Message[serverNum]; // 下標(biāo)為server編號(hào)-1，值為目前仍在處理的 message信息// 首先將消息按時(shí)間排序Arrays.sort(messages, Comparator.comparingInt(o -> o.time));int lastProcessIdx = -1; // 上次分配執(zhí)行的服務(wù)器，從-1開(kāi)始// 依次處理 messagesfor (Message message : messages) {// 首先更新時(shí)間updateTime(message.time, isBusy, processingMsg, serverNum);// 從 lastProcessIdx 下一個(gè)位置開(kāi)始，循環(huán)找到第一個(gè)空閑的server// 按順序循環(huán)分配服務(wù)器：i最大值可為 2 * serverNum，使用 i % serverNum 得到對(duì)應(yīng)循環(huán)的下標(biāo)for (int i = lastProcessIdx + 1; i < 2 * serverNum; i++) {// 不忙，說(shuō)明找到空閑的Serverif (!isBusy[i % serverNum]) {processingMsg[i % serverNum] = message; // message添加到processingMsgserverLoad[i % serverNum] += message.load; // 計(jì)算該server的總負(fù)載值isBusy[i % serverNum] = true; // 標(biāo)記該server為忙碌lastProcessIdx = i % serverNum; // 記錄下 lastProcessIdx 以下次循環(huán)使用break;}}}// 統(tǒng)計(jì)結(jié)果List<int[]> 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升序// 生成答案List<Integer> ansList = new ArrayList<>();ansList.add(idLoadArrList.get(0)[0]);int maxLoad = idLoadArrList.get(0)[1];int i = 1;// 將與最大值相等的serverId加入結(jié)果集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));}
}