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

题意

有 n 台计算机，每台有固定算力。

每个任务会在时刻 a 被分配到指定机器 b，持续 c 秒，占用算力 d。

如果分配时该机器剩余算力不足，就输出 -1；否则任务成功开始运行，输出分配后的剩余算力。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Task {
    ll end_time;
    ll cost;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<ll> cap(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> cap[i];
    }

    vector<vector<Task> > tasks(n + 1);
    vector<ll> used(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;

        vector<Task> alive;
        used[b] = 0;
        for (Task t : tasks[b]) {
            if (t.end_time > a) {
                alive.push_back(t);
                used[b] += t.cost;
            }
        }
        tasks[b].swap(alive);

        if (cap[b] - used[b] < d) {
            cout << -1 << '\n';
            continue;
        }

        tasks[b].push_back({a + c, d});
        used[b] += d;
        cout << cap[b] - used[b] << '\n';
    }

    return 0;
}

最直接的想法是：对每台机器维护当前正在运行的任务列表。

每来一个新任务，就先把这台机器上所有已经结束的任务删掉，再看剩余算力是否够。

真正的问题只在于：

怎样快速找到“已经结束的任务”

因为每个任务一旦开始，它的结束时刻 a + c 就确定了，所以对每台机器维护一个按结束时刻排序的小根堆即可。

处理一个新任务 (a, b, c, d) 时：

不断弹出 b 号机器里所有 end_time <= a 的任务
同时把这些任务占用的算力从 used[b] 里减掉
判断 cap[b] - used[b] 是否至少为 d
如果够，就把新任务压入堆里

因为每个任务只会入堆一次、出堆一次，所以总复杂度是可控的。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005;

struct Node {
    ll end_time;
    ll cost;

    bool operator < (const Node &other) const {
        return end_time > other.end_time;
    }
};

int n, m;
ll cap[MAXN];
ll used[MAXN];
priority_queue<Node> pq[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> cap[i];
    }

    for (int i = 1; i <= m; i++) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;

        // 先释放掉这台机器上所有已经结束的任务。
        while (!pq[b].empty() && pq[b].top().end_time <= a) {
            used[b] -= pq[b].top().cost;
            pq[b].pop();
        }

        if (cap[b] - used[b] < d) {
            cout << -1 << '\n';
            continue;
        }

        used[b] += d;
        pq[b].push({a + c, d});
        cout << cap[b] - used[b] << '\n';
    }

    return 0;
}

复杂度

每个任务最多入堆一次、出堆一次，所以总复杂度是 $O(m log m)$ 级别。

更准确地说，是所有机器堆操作次数总共 $O(m)$ 次，每次 $O(log m)$ 。

空间复杂度是 $O(m)$ 。

总结

这题本质上是“按机器分组的事件模拟”。

关键不是复杂数据结构，而是抓住：

结束任务要按最早结束的先释放

于是每台机器用一个小根堆就足够了。

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

目录

题意

思路

代码

复杂度

总结