自动搬运

查看原文

来自洛谷，原作者为

	Kimi 銃弾の雨で、あなたたちを苦痛から救済しよう

搬运于2025-08-24 22:50:31，当前版本为作者最后更新于2024-09-29 17:18:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9661题解

前言

这翻译的什么东西

题意

给一个有 $n$ 个点的完全图，每个点有一个点值。每次进行一次操作，操作是这样的：如果一个点的点权大于与它相连的边数，就另权值减去与它相连的边数，并给与它相连的点点权加一。

如果此操作能不断进行下去，输出 Recurrent，否则按操作完的序列输出。

思路

对于 $i\in \left \{ 1, 2, \dots n \right \}$ 有 $A[i] \ge i - 1$ 就有循环，但是会有极端数据出现，如样例二，所以先把大于 $n - 1$ 的减掉，加回去，排序，特判就没问题了。

操作用优先队列来模拟就好了，比较简单，看代码理解理解就好。

代码

//code by Kimi
#include<bits/stdc++.h>
#define int long long
#define sept fixed << setprecision(4)
#define debug(x) cerr << (#x) << endl
#define pb emplace_back
#define endl '\n'
#define WA AC
using namespace std;
const int maxn = 5e5 + 10;
int n, v;
int A[maxn], B[maxn], ans[maxn];
priority_queue<pair<int, int> > q;
void check(){
	int tmp;
	for(int i = 1; i <= n; i++) B[i] = A[i];
	for(int i = 1; i <= n; i++){
        tmp = B[i] / (n - 1);
        v += tmp;
		B[i] %= (n - 1), B[i] -= tmp;
    }
    for(int i = 1; i <= n; i++) B[i] += v;
    sort(B + 1, B + n + 1);
    for(int i = 1; i <= n; i++){
    	if(B[i] < i - 1) return;
	}
	cout << "Recurrent" << endl;
	exit(0);
}
void input(){
	srand(19491001);
    ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> A[i];
	check();
	v = 0;
}
void init(){}
signed main(){
	init();
	input();
	for(int i = 1; i <= n; i++) q.push({A[i], i});
	while(q.top().first + v >= n - 1){
        int top1 = q.top().first, top2 = q.top().second;
		q.pop();
        top1 += v, top1 -= (n - 1), v++;
        q.push({top1 - v, top2});
    }
    while(q.size()){
        auto top = q.top();
		q.pop();
        ans[top.second] = top.first + v;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
	return 0;
}