ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 AE: 负载均衡

内存限制：128 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：30 通过：24
返回比赛提交提交记录

题目描述

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

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

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


题目链接：P8755 [蓝桥杯 2021 省 AB2] 负载均衡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

输入格式

输入的第一行包含两个整数 $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$ 行，每行包含一个数，对应每次任务分配的结果。

输入样例 复制 

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

**【评测用例规模与约定】**

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

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

对于所有评测用例, $1 \leq n, m \leq 2\times 10^5,1 \leq a_{i}, c_{i}, d_{i}, v_{i} \leq 10^{9}, 1 \leq b_{i} \leq n$。 

分类标签