题目传送门: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; }
Comments NOTHING