P9321 [EGOI2022] Data Centers / 数据中心 题解

Miyamizu_Mitsuha · 2023-07-08 19:25:28 · 题解

思路

双指针解决。

用一个循环遍历所有的数据中心，根据当前数据中心的可用机器数和剩余机器数，选择分配机器数并存在 temp 数组中。具体的分配规则如下：

• 如果 (m_ {left} - me) > (m_ {right} 且 left \geq copies，或者 right \gt n，选择分配 (m _ {left} - me) 个机器，并将 left 指针右移一位。
• 否则，选择分配 m _ {right} 个机器，并将 right 指针右移一位。

完成所有服务的处理后，将 temp 数组中的值复制回 m 数组，得到每个数据中心剩余的机器数。最后，使用一个循环按降序输出 m 数组中的值，即为每个数据中心剩余的机器数。

复杂度 O(ns)。

代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ui unsigned int

using namespace std;

int m[100005], temp[100005];

int main() {
    int n, s;
    scanf("%d%d", &n, &s);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &m[i]);
    }

    sort(m + 1, m + n + 1);
    reverse(m + 1, m + n + 1);

    while (s--) {
        int me, copies;
        scanf("%d%d", &me, &copies);

        int left = 1, right = copies + 1;

        for (int i = 1; i <= n; i++) {
            if ((m[left] - me) > m[right] && left <= copies || right > n) {
                temp[i] = m[left] - me;
                left++;
            } else {
                temp[i] = m[right];
                right++;
            }
        }

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

    for (int i = 1; i <= n; i++)
    printf("%d ", m[i]);

return 0;
}