自动搬运

查看原文

来自洛谷，原作者为

	kangli 这个家伙不懒，但还是什么也没有留下

搬运于2025-08-24 21:47:14，当前版本为作者最后更新于2019-07-28 08:43:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【提示】：本题解并非本题的正解，无法通过部分 hack 数据。但其思想具有启发性，故保留在此，供大家参考。

我们考虑到题干所给的5个条件都必须满足。

不妨考虑随机贪心。

由于糖果数量要尽量的小且每个小朋友糖果数量都要大于等于$1$，我们初始时先设所有小朋友糖果数为$1$。

然后循环每一个询问满足条件，但是考虑到后面条件满足了会影响前面的条件，所以可以让条件跑很多次更新答案。

每次更新时，采用贪心的思想，增加的糖果尽量少。

为什么不要减少糖果呢？因为初始的时候小朋友的糖果为最少了，所以后续条件不能让他再少了。

随机贪心大约$200$次左右，最后在循环一次判断是否满足题意。

不喜勿喷，谢谢。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct candy{
	int X,A,B;
}q[101010];
int n,k;
int a[101010];
int main()
{
	//freopen("a.in","r",stdin);
	cin>>n>>k;
	for (int i=1; i<=k; i++){
		scanf("%d%d%d",&q[i].X,&q[i].A,&q[i].B);
	}
	for (int i=1; i<=n; i++) a[i]=1;
	for (int T=1; T<=200; T++){
		for (int i=1; i<=k; i++){
			if (q[i].X==1) {
				if (a[q[i].A]>a[q[i].B]) a[q[i].B]=a[q[i].A];
				else a[q[i].A]=a[q[i].B];
			}
			else if (q[i].X==2){
				if (a[q[i].A]>=a[q[i].B]) a[q[i].B]=a[q[i].A]+1;
			}
			else if (q[i].X==3){
				if (a[q[i].A]<a[q[i].B]) a[q[i].A]=a[q[i].B];
			}
			else if (q[i].X==4){
				if (a[q[i].A]<=a[q[i].B]) a[q[i].A]=a[q[i].B]+1;
			}
			else if (q[i].X==5){
				if (a[q[i].A]>a[q[i].B]) a[q[i].B]=a[q[i].A];
			}
		}
	}
	for (int i=1; i<=k; i++){
		if (q[i].X==1) {
				if (a[q[i].A]>a[q[i].B]) {cout<<"-1";return 0;}
			}
			else if (q[i].X==2){
				if (a[q[i].A]>=a[q[i].B]) {cout<<"-1";return 0;}
			}
			else if (q[i].X==3){
				if (a[q[i].A]<a[q[i].B]) {cout<<"-1";return 0;}
			}
			else if (q[i].X==4){
				if (a[q[i].A]<=a[q[i].B]) {cout<<"-1";return 0;}
			}
			else if (q[i].X==5){
				if (a[q[i].A]>a[q[i].B]) {cout<<"-1";return 0;}
			}
	}
	long long ans=0;
	for (int i=1; i<=n; i++) ans+=a[i];
	cout<<ans<<endl;
	return 0;
}