【CodeForces 534D】Handshakes

真·skysys

于 2016-10-13 08:34:22 发布

阅读量437

点赞数

分类专栏：算法与数学文章标签：贪心

请明确标注出处

本文链接：https://blog.csdn.net/qq_33583069/article/details/52803632

版权

算法与数学专栏收录该内容

469 篇文章 ¥29.90 ¥99.00

订阅专栏

超级会员免费看

本文详细介绍了如何解决CodeForces编程竞赛中的534D题目——握手问题。通过运用贪心算法，解析了如何有效地计算在一系列握手事件后，每个人握手的次数，确保没有交叉和遗漏。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include<bits/stdc++.h>
using namespace std;
vector<int> e[200010];
int n,id[200010],idx,cnt[200010],tot,up;
int a[200010],st[200010];
bool flag = true;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		cnt[a[i]]++;
		e[a[i]].push_back(i);
		up = max(up,a[i]);
	}	
	for(int i=0;i<=up;i++)
	{
		if(cnt[i]==0)
		{
			flag = false;
			break;
		}
	}
	if(!flag){
		puts("Impossible");
		return 0;
	}
	int now = 0;
	while(idx<n)
	{	
		if(now<0||st[now]>=e[now].size())
		{
			flag = false;
			break;
		}	
		id[++idx]=e[now][st[