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

题目大意

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

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

思路

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

因为每执行了$n$次操作，一定存在一个点，它至少被分了$n?1$个饼干,也存在一个点，它至少被分了$n?2$个饼干，紧接着，有$n?3,n?4,...$个饼干，而我们挑那个被分了$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);now.val = (now.val + cnt) % (n - 1) - tmp - cnt; 这个点给其它点分tmp个饼干，而这是加在cnt上的，为了防止多加，那就让这个点的数量减去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;
}