ICPC澳门站F - Sandpile on Clique（模拟）

题目传送门：F-Sandpile on Clique_第46屆ICPC 東亞洲區域賽（澳門）(正式賽） (nowcoder.com)

我去，模拟，卡了好久。

题目大意

有一个完全图，如果某个点的球数量大于入度（就是N - 1），那么这个点的值就给每一个出点一个球，自身就减少N - 1个球，问能否达到“每个点的球数量都小于N - 1”或者会出现无限循环。

思路

每次分散，给N - 1个点 + 1，其实都是扫描线（N - 1）在减小，每次如果有点的值大于等于扫描线，那么这个点就要分散，如果扫描线小于等于0（这是不存在的情况，因为不存在任何一个点小于0）了，也就是说进行了N次模拟，那么一定存在循环。

注意保存一个修正量fix，在输出的时候加上，这是为了降低给N - 1个点 + 1的复杂度。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;//{index, value}
const int maxn = 5e5 + 9;

struct cmp{bool operator ()(PII &a, PII &b){return a.se < b.se;}};
priority_queue<PII,vector<PII>, cmp> pq;
int h[maxn];

signed main()
{
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld", h + i);
		pq.push({i, h[i]});
	}
	int limit = N - 1;//每个点的值都应该小于N - 1,，否则就要分散给其他点 
	int fix = 0;//修正量 
	for(int i = 1;i <= N; ++ i)//如果N次分散都没有得到结果，那么一定是Recurrent 
	{
		//因为假设不存在修正量，N次分散之后扫描线到了0，一定不存在小于0的值 
		while(h[pq.top().fi] != pq.top().se)pq.pop();
		int idx = pq.top().fi, val = pq.top().se;
		pq.pop();
		
		if(val < limit)//满足要求 
		{
			for(int i = 1;i <= N; ++ i)
				printf("%lld%c",h[i] + fix, i == N ? '\n' : ' ');
			return 0;
		}
		
		limit --;
		fix ++;
		h[idx] -= N;
		pq.push({idx, h[idx]});
	}
	printf("Recurrent\n");
	return 0;
}