课程网站开发背景和意义,硬件开发和软件开发哪个工资高,新闻最近新闻10条,云购网站开发负载平衡题目描述有 \\(n\\) 台计算机#xff0c;第 \\(i\\) 台计算机的运算能力为 \\(v_i\\)。有一系列的任务被指派到各个计算机上#xff0c;第 \\(i\\) 个任务在 \\(a_i\\) 时刻分配#xff0c;指定计算机编号为 \\(b_i\\)#xff0c;耗时为 \\(c_i\\) 且算力消耗为 \\…负载平衡题目描述有 \\(n\\) 台计算机第 \\(i\\) 台计算机的运算能力为 \\(v_i\\)。有一系列的任务被指派到各个计算机上第 \\(i\\) 个任务在 \\(a_i\\) 时刻分配指定计算机编号为 \\(b_i\\)耗时为 \\(c_i\\) 且算力消耗为 \\(d_i\\)。如果此任务成功分配将立刻开始运行期间持续占用 \\(b_i\\) 号计算机 \\(d_i\\) 的算力持续 \\(c_i\\) 秒。对于每次任务分配如果计算机剩余的运算能力不足则输出 \\(-1\\)并取消这次分配否则输出分配完这个任务后这台计算机的剩余运算能力。数据范围\\(1 \\leq n,m \\leq 200000,1 \\leq a_i,c_i,d_i,v_i \\leq 10^9,1 \\leq b_i \\leq n\\)分析对于每个时刻被选中的计算机我们需要知道它此时的算力有多少而此时的算力在之前可能被消耗过需要恢复那么我们考虑对于每一个计算机维护一个小根堆每次分配任务的时候将\\(\\leq a\\)的任务弹出然后恢复算力判断即可。代码#include using namespace std;typedef pair PII;const int N 2e5 10;priority_queue ,greater q[N];#define mk(x,y) make_pair(x,y)int n,m;int v[N];int a,b,c,d;int main () {ios :: sync_with_stdio(false);cin n m;for(int i 1;i n; i) {cin v[i];}while(m --) {cin a b c d;while(q[b].size() and q[b].top().first a) {v[b] q[b].top().second;q[b].pop();}if(v[b] d) puts(-1);else {q[b].push(mk(a c,d));v[b] - d;printf(%d\\n,v[b]);}}return 0;}
