ICPC澳门站F – Sandpile on Clique(模拟)

发布于 2022-04-04  1112 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09