【洛谷 P8755】[蓝桥杯 2021 省 AB2] 负载均衡 题解（优先队列+结构体+模拟）

[蓝桥杯 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 题）。

---

思路

首先定义一个名为Stask的结构体来存储每个任务的信息，包括任务分配的时刻a，耗时c以及消耗的算力d。然后定义一个优先级队列，队列中的元素为Stask类型，队列的比较函数为Scmp，Scmp的比较规则是：任务开始时间加上耗时越小的任务优先级越高。

然后从输入中读取计算机的数量n和任务的数量m。接着，读取每台计算机的运算能力v[i]。之后，对每个任务进行处理。每个任务在读取时刻a，分配的计算机编号b，耗时c以及消耗的算力d后，创建一个Stask对象tsk。

接着，检查分配给该任务的计算机上是否有正在运行的任务，如果有，那么就检查这些任务是否已经完成。完成的任务会被从队列中移除，并减少相应的算力消耗。这个过程会一直进行，直到当前计算机上没有任务，或者队列顶部的任务还没有完成。

然后，如果当前计算机的剩余算力足够执行新的任务，就把新的任务添加到队列中，并增加相应的算力消耗。然后输出当前计算机的剩余运算能力。如果剩余算力不足以执行新的任务，就输出-1。

---

AC代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n, m;
int v[N];
ll sum[N];

struct Stask {
	// a时刻分配
	int a;
	// 耗时c
	int c;
	// 消耗算力d
	int d;
};

struct Scmp {
	bool operator()(const Stask &x, const Stask &y) const {
		return x.a + x.c > y.a + y.c;
	}
};

priority_queue<Stask, vector<Stask>, Scmp> pq[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	for (int i = 1; i <= m; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		Stask tsk = {a, c, d};
		if (pq[b].size()) {
			Stask t = pq[b].top();
			while (t.a + t.c <= tsk.a) {
				sum[b] -= t.d;
				pq[b].pop();
				if (pq[b].empty()) {
					break;
				}
				t = pq[b].top();
			}
		}
		if (sum[b] + tsk.d <= v[b]) {
			pq[b].push(tsk);
			sum[b] += tsk.d;
			cout << v[b] - sum[b] << "\n";
		} else {
			cout << -1 << "\n";
		}
	}
	return 0;
}