当可以经过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;
}