【ICPC 2022 澳门站】F题 Sandpile on Clique 题解

题目大意

有一个 $n$ 个点的完全图，每个点上有 $a_i$ 个饼干。我们可以任意选择一个点，让它给每个相邻的节点分一个饼干，如果不够，那就无法执行此操作。

问我们是否可以一直进行此操作？如果不能，那就输出最终每个点剩余的饼干的数量（即所有点的饼干都不够 $n-1$ 个）。

思路

其实模拟几次就可以看出规律来，如果我们至少进行了 $n$ 次这个操作，那我们就能一直执行下去。

因为每执行了 $n$ 次操作，一定存在一个点，它至少被分了 $n-1$ 个饼干，也存在一个点，它至少被分了 $n-2$ 个饼干，紧接着，有 $n-3, n-4, \ldots$ 个饼干。而我们挑那个被分了 $n-1$ 次饼干的点再分一次，那么就又出现了被分了 $n-1$ 次的点……，那么这个操作就可以一直执行下去。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int maxN = 5e5 + 5;
int n, cnt, t[maxN];

struct Node {
    int index;
    long long val;
    bool operator < (const Node &x) const {
        return val > x.val;
    }
}a[maxN];

multiset<Node> s;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i].val);
        a[i].index = i;
        s.insert(a[i]);
    }
    long long cnt = 0; bool succ = true; // 累计分出来多少个饼干
    for(int i = 1; i <= n; ++i) {
        Node now = *s.begin(); 
        if(now.val + cnt < n - 1) { //分不了了
            succ = false;
            for(multiset<Node> :: iterator it = s.begin(); it != s.end(); it++) 
                a[it->index].val = it->val + cnt;
            break;
        }
        long long tmp = (now.val + cnt) / (n - 1);
        // 这个点给其它点分tmp个饼干，而这是加在cnt上的，为了防止多加，那就让这个点的数量减去tmp，减去cnt是为了减去它之前分饼干带来的影响
        now.val = (now.val + cnt) % (n - 1) - tmp - cnt;
        cnt += tmp;
        s.erase(s.begin()); s.insert(now);
    }
    if(succ)
        printf("Recurrent");
    else {
        printf("%d", a[1].val);
        for(int i = 2; i <= n; ++i)
            printf(" %d", a[i].val);
    }
    return 0;
}