[蓝桥杯 2021 省 AB2] 负载均衡

题目描述

有 $n$ 台计算机，第 $i$ 台计算机的运算能力为 $v_i$ 。

有一系列的任务被指派到各个计算机上，第 $i$ 个任务在 $a_i$ 时刻分配，指定计算机编号为 $b_i$, 耗时为 $c_i$ 且算力消耗为 $d_i$。如果此任务成功分配，将立刻开始运行, 期间持续占用 $b_i$ 号计算机 $d_i$ 的算力, 持续 $c_i$ 秒。

对于每次任务分配，如果计算机剩余的运算能力不足则输出 $-1$，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

输入格式

输入的第一行包含两个整数 $n,m$，分别表示计算机数目和要分配的任务数。

第二行包含 $n$ 个整数 $v_1,v_2,\cdots v_n$，分别表示每个计算机的运算能力。

接下来 $m$ 行每行 $4$ 个整数 $a_i,b_i,c_i,d_i$，意义如上所述。数据保证 $a_i$ 严格递增，即 $a_i<a_{i+1}$ 。

输出格式

输出 $m$ 行，每行包含一个数，对应每次任务分配的结果。

样例 #1

样例输入 #1

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

样例输出 #1

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$ 个任务，剩余算力足够，且恰好用完。

【评测用例规模与约定】

对于 $20\%$ 的评测用例, $n,m\le 200$。

对于 $40\%$ 的评测用例, $n,m\le 2000$。

对于所有评测用例, $1\le n,m\le 2\times 10^5,1\le a_i,c_i,d_i,v_i\le 10^9,1\le b_i\le n$。

蓝桥杯 2021 第二轮省赛 A 组 H 题（B 组 I 题）。

---

思路

呀呀呀，任务写成进程了呀呀呀呀学操作系统学傻了

1. 有n个计算机，有算力，如果算力足够可以直接加入计算机中，如果算力不够就不行，这就要求我们实时的更新在这个计算机中的进程，把已经计算完的进程及时的退出，那就要求我们要知道在每个计算机中结束时间最早的是哪一个进程，然后将他弹出，所以可以使用小根堆来代表计算机储存每个进程。
2. 这个进程有用的信息就是，结束时间和算力消耗，每个进程的使用的编号可以用数组编号对应所以可以用pair数组来存，当然也可以用结构体来存。
3. 实时的模拟进程就完事了，没有别的什么的需要注意的。

全部代码：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 2e5 + 10;
int n, m;
int s[N];
// pair<结束时间，消耗算力>                                                         // 存储计算机的当前算力
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q[N]; // 小根堆 pair先比较第一个，第一个相同比较第二个

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i]; // 运算能力
    while (m--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d; // 分配时刻，计算机编号，耗时，算力消耗
        // 维护
        while (q[b].size() && q[b].top().first <= a) // 最小的右端点小于算完了
        {
            s[b] += q[b].top().second; // 结束运算上一个任务，返回算力
            q[b].pop();                // 弹出上一个任务
        }
        if (s[b] < d)
            printf("-1\n"); // 算力不够
        else
        {
            q[b].push({a + c, d}); // 将新的任务加入
            s[b] -= d;
            printf("%d\n", s[b]);
        }
    }
    return 0;
}