问题描述
有 n 台计算机，第 i 台计算机的运算能力为 vi。
有一系列的任务被指派到各个计算机上，第 i 个任务在 ai 时刻分配，指定计算机编号为 bi，耗时为 ci 且算力消耗为 di。
如果此任务成功分配，将立刻开始运行，期间持续占用 bi 号计算机 di 的算力，持续 ci 秒。
对于每次任务分配，如果计算机剩余的运算能力不足则输出 −1，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。
输入格式
输入的第一行包含两个整数 n,m，分别表示计算机数目和要分配的任务数。
第二行包含 n 个整数 v1,v2,⋅⋅⋅vn，分别表示每个计算机的运算能力。
接下来 m 行每行 44 个整数 ai,bi,ci,di，意义如上所述。数据保证 ai 严格递增，即 ai<ai+1。
输出格式
输出 m 行，每行包含一个数，对应每次任务分配的结果。
数据范围
对于 20% 的评测用例，n,m≤200。
对于 40% 的评测用例，n,m≤2000。
对于所有评测用例，1≤n,m≤200000，1≤ai,ci,di,vi≤109，1≤bi≤n。
输入样例：
2 6 5 5 1 1 5 3 2 2 2 6 3 1 2 3 4 1 6 1 5 1 3 3 6 1 3 4
输出样例：
2 -1 -1 1 -1 0
样例解释
时刻 1，第 1 个任务被分配到第 1 台计算机，耗时为 5，这个任务时刻 6 会结束，占用计算机 1 的算力 3。
时刻 2，第 2 个任务需要的算力不足，所以分配失败了。
时刻 3，第 1 个计算机仍然正在计算第 1 个任务，剩余算力不足 3，所以失败。
时刻 4，第 1 个计算机仍然正在计算第 1 个任务，但剩余算力足够，分配后剩余算力 1。
时刻 5，第 1 个计算机仍然正在计算第 1,4 个任务，剩余算力不足 4，失败。
时刻 6，第 1 个计算机仍然正在计算第 4 个任务，剩余算力足够，且恰好用完。
思路
这道题如果我们用暴力同样只能得一部分分数，所以我们可以用优先队列来模拟，将时间复杂度降低。
//优先队列 priority_queue<int,vector<int>,less<int>> maxHeap; //大顶堆（默认） priority_queue<int,vector<int>,greater<int>> minHeap; //小顶堆
这里我们要用到的是最小堆，在 C++ 中可以直接调用上面函数即可，我们的目的是将结束时刻最靠前的任务放在堆顶，方便我们处理。这样做的原因是什么，我们只看一个计算机的处理过程你就明白了：
我们只在该计算机任务开始时，处理该时刻以前已经完成的任务，只用将结束时刻小于当前时刻的任务删除并释放算力即可，也就是将堆顶任务的结束时刻与当前时刻进行比较，然后再去判断当前时刻任务是否满足要求，这样就不用去枚举所有时刻从而降低时间复杂度了。
代码
#include <bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int, int> PII; //{结束时刻，消耗算力} const int N = 200010; int s[N], n, m; //我们用优先队列来保存所有计算机的任务，用下标即计算机id就可以找到对应任务了 //最小堆优先队列会将结束时刻最靠前的任务放在最顶端 priority_queue<PII, vector<PII>, greater<PII>> q[N]; //最小堆 int main() { cin >> n >> m; //输入每个计算机的运算能力 for (int i = 1; i <= n; i++) scanf("%d", &s[i]); //处理每一个任务 while (m--) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); //释放当前时刻前已经完成的任务的算力 while (!q[b].empty() && q[b].top().x <= a) { s[b] += q[b].top().y; q[b].pop(); } //如果当前剩余算力小于所需算力，则输出-1 if (s[b] < d) puts("-1"); //否则，减去所需算力并加入优先队列中 else { s[b] -= d; q[b].push({a + c, d}); printf("%d\n", s[b]); } } return 0; }
