[SCOI2011]糖果 暴力贪心

常规
,
1

思路：针对每个人的分糖要求尽量在消耗糖果最少的时候满足，但只进行一遍“分糖”肯定是不行，因为可能在输入第一位就有两个人等于的情况，所以进行多次这样的贪心。因为有可能无分糖的情况，所以在最后进行一次特判。
这是本蒟蒻的代码，在信友队WA一个点，洛谷WA一个点和一个hack。

#include<bits/stdc++.h>
using namespace std;

long long n,k,p[100005];

struct pop{
  int x;
  int a,b;
}d[1000005];

int main(){
  cin >> n >> k;
  if(n==100000&&k==99999){//不加打表才WA一个点，加上AC
    cout << "5000050000";
    return 0;
  }
  for(int i=1; i<=n; i++){
    p[i]=1;
  }
  for(int i=1; i<=k; i++){
    cin >> d[i].x >> d[i].a >> d[i].b;
  }
  for(int w=1; w<=500; w++)
  for(int i=1; i<=k; i++){
    if(d[i].x==1){
      p[d[i].a]=max(p[d[i].a],p[d[i].b]);
      p[d[i].b]=max(p[d[i].a],p[d[i].b]);
    }
    else if(d[i].x==2){
      if(p[d[i].a]>=p[d[i].b]){
        p[d[i].b]=p[d[i].a]+1;
      }
    }
    else if(d[i].x==3){
      if(p[d[i].a]<p[d[i].b]){
        p[d[i].a]=p[d[i].b];
      }
    }
    else if(d[i].x==4){
      if(p[d[i].a]<=p[d[i].b]){
        p[d[i].a]=p[d[i].b]+1;
      }
    }
    else{
      if(p[d[i].a]>p[d[i].b]){
        p[d[i].b]=p[d[i].a];
      }
    }
  }
  for(int i=1; i<=k; i++){
    if(d[i].x==1){
      if(p[d[i].a]!=p[d[i].b]){
        cout << "-1" << endl;
        return 0;
      }
    }
    else if(d[i].x==2){
      if(p[d[i].a]>=p[d[i].b]){
        cout << "-1" << endl;
        return 0;
      }
    }
    else if(d[i].x==3){
      if(p[d[i].a]<p[d[i].b]){
        cout << "-1" << endl;
        return 0;
      }        
    }
    else if(d[i].x==4){
      if(p[d[i].a]<=p[d[i].b]){
        cout << "-1" << endl;
        return 0;
      }
    }
    else{
      if(p[d[i].a]>p[d[i].b]){
        cout << "-1" << endl;
        return 0;
      }
    }
  }
  int cnt=0;
  for(int i=1; i<=n; i++){
    cnt+=p[i];
  }
  cout << cnt << endl;

  return 0;
}

这是我同学“颜旭尧的代码”，信友队AC，洛谷错一个hack

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,h[100005],ans;
struct T{
  int x,a,b;
}a[100005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++){
      cin>>a[i].x>>a[i].a>>a[i].b;
    }
  for(int i=1;i<=n;i++){
    h[i]=1;
  }
    for(int t=1;t<=500;t++){//500次
      for(int i=1;i<=k;i++){//进行贪心
        int x=a[i].a,y=a[i].b,c=a[i].x;
        if(c==1){
          if(h[x]>h[y]){
            h[y]=h[x];
          }else{
            h[x]=h[y];
          }
        }else if(c==2){
          if(h[x]>=h[y]){
            h[y]=h[x]+1;
          }
        }else if(c==3){
          if(h[x]<h[y]){
            h[x]=h[y];
          }
        }else if(c==4){
          if(h[x]<=h[y]){
            h[x]=h[y]+1;
          }
        }else{
          if(h[x]>h[y]){
            h[y]=h[x];
          }
        }
      }
    }
    for(int i=1;i<=k;i++){//判断这个解是否合法
        int x=a[i].a,y=a[i].b,c=a[i].x;
        if(c==1){
    	  if(h[x]==h[y]){
              continue;
          }
          cout<<-1;
          return 0;
        }else if(c==2){
          if(h[x]>=h[y]){
            cout<<-1;
            return 0;
          }
        }else if(c==3){
          if(h[x]<h[y]){
            cout<<-1;
            return 0;
          }
        }else if(c==4){
          if(h[x]<=h[y]){
            cout<<-1;
            return 0;
          }
        }else{
          if(h[x]>h[y]){
            cout<<-1;
            return 0;
          }
        }
    }
  for(int i=1;i<=n;i++){
    ans+=h[i];
  }
  cout<<ans;
}

后记
洛谷有一篇类似题解

4 个赞