题目描述
有一批数据包需要传输，每个数包大小不一样，传输需要不同的时长，现在有N个传输通道，每个通道的大小也不一样，通道只能传输小于等于自己大小的数据包，不同通道可以同时传输数据包，通道中可以缓存多个数据包，当新任务来时，可以先进入缓存队列等待发送，问最短需要多长时间能够传输完成，通道会确保所有数据都可以传输
输入
第一行M N, M表示队列长度，N表示传输通道数
第二行有N个数，表示每个通道的大小P
第三行有M个数，表示每个数据包的大小Q
第四行有M个数，表示每个数据包传输时长S
1 <= M, S, P, Q <= 10000 ; 1 <= N <= 1000输出
输出传输完所有数据包需要的最短时长
样例1
输入：
5 2
5 3
1 4 5 2 3
1 6 10 3 4
输出：16
解释：数据包3进入通道1、数据包2进入通道1，数据包5进入通道2，数据包4进入通道2， 数据包1进入通道2； 通道1的传输时长是10+6=16，通道2的传输时长是3+2+1=8，这样最短时长就为16
样例2
输入：
3 2
6 13
2 11 5
3 25 14
输出：25
解释：数据包2进入通道2、数据包3进入通道1，数据包1进入通道1； 通道1的传输时长是14+3=17，通道2的传输时长是25，这样最短时长就为25
代码
//该题贪心算法可以AC，可能笔试的测试数据比较简单，有人给出了该代码过不了的测试案例
let readlineSync = require('readline-sync');
readlineSync.setDefaultOptions({ prompt: '' })
let readline = readlineSync.prompt
let fastTransfer = (M, N, channels, numsQ) => {
numsQ.sort((a, b) => {
if(a[1] === b[1]) {
return a[0] - b[0];//如果传输时长一样，则数据小的排前面
}
return b[1] - a[1];//因为要先传输耗时长的数据，再依次传输耗时短的数据
});
let max = 0;
for(let data of numsQ) {
let minTime = Number.MAX_VALUE;
let select = 0;
for(let i = 0; i < N; i++) {
if(channels[i][0] >= data[0]) {//如果当前通道 i能传输当前数据
if(channels[i][1] < minTime) {
select = i;//优先选择所有通道中已传输时长最短的那个
minTime = channels[i][1];
} else if(channels[i][1] === minTime && channels[select][0] > channels[i][0]) {
select = i; //如果已选择的通道与当前通道的时长相等，则选择更小的通道传输该数据
}
}
}
channels[select][1] += data[1];
max = Math.max(max, channels[select][1]);//不断记录传输时长最长的那个通道
}
return max;
}
let firstLine = readline().split(" ");
let M = parseInt(firstLine[0]);//队列长度，即数据包个数
let N = parseInt(firstLine[1]);//通道数
let secondLine = readline().split(" ");//通道的大小
let thirdLine = readline().split(" ");//数据的大小
let fourthLine = readline().split(" ");//数据传输时长
let channels = [];//通道大小
let numsQ = [];//数据包大小和传输时间
for(let c of secondLine) {
channels.push([parseInt(c), 0]);
}
for(let i = 0; i < M; i++) {
numsQ.push([parseInt(thirdLine[i]), parseInt(fourthLine[i])]);
}
let res = fastTransfer(M, N, channels, numsQ);
console.log("res = " + res);
//题中的测试案例都能过，但是这个案例过不了
//5 2
//100 100
//7 6 4 3 2
//7 6 4 3 2
//程序输出12，最优解应该是11（7 + 4, 6 + 3 + 2）
