题解 P3275 【[SCOI2011]糖果】

kangli · 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;
}