ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年4月4日 997点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ icpc 模拟 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号