自动搬运

查看原文

来自洛谷，原作者为

	Miyamizu_Mitsuha 再也追不上曾经那个被寄予厚望的自己.

搬运于2025-08-24 22:47:20，当前版本为作者最后更新于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;
}