题解 - 帖子 - CQUPT OJ

当可以经过n-1次的操作，则本题为Forever,否则输出笑容度。

证明：对于任何连续的 n − 1 次操作，必须至少有一个节点不包括在这 n − 1 次中。对于此节点，它必须接收 n − 1 个笑容度而不会丢失任何一个笑容度。然后它就会达到Forever状态。

彩蛋：数据有些难造，没卡住一些非正解。

参考代码


#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int MaxN = 5e5 + 3;

priority_queue<pair<long long, int> > p;

pair<int, long long> ans[MaxN];

long long d;

int tot;

void Print() {
    while (p.size()) {
        ans[++tot] = { p.top().second, p.top().first + d };
        p.pop();
    }
    sort(ans + 1, ans + tot + 1);
    for (int i = 1; i <= tot; i++) {
        cout << ans[i].second << ' ';
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        p.push({ x, i });
    }
    for (int i = 1; i <= n; i++) {
        pair<long long, int> tmp = p.top();
        long long s = tmp.first + d;
        d += s / (n - 1);
        if (s < n - 1) {
            Print();
            return 0;
        }
        p.pop();
        p.push({ s % (n - 1) - d, tmp.second });
    }
    cout << "Forever";
    return 0;
}