HDU 5353 模拟

题意

N个人首尾相连，每个人可以给旁边的人一个SODA，也可以从旁边的人那里拿一个SODA。两个人之间给或拿只能操作一次，求是否存在操作方案，使得最后所有人SODA数目相同。

题解

模拟。第一个人可能从第二个人那里拿一个SODA，也可能给第二个人一个SODA，也可能不操作。模拟三种情况即可。

注意事项

需要注意某一个人的SODA初始数与平均值差2，依然有可能经过几次操作后，每个人的SODA数目相同。

代码

#include <iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; int num[100010]; struct Node{ int from,to; }; int s1[100010],s2[100010]; int u[100010],v[100010]; int k,n; bool give(int *nu){ int i=2; for(;i<=n;i++){ if(nu[i]==1){ nu[i]--; nu[i%n+1]++; u[k]=i; v[k++]=i%n+1; }else if(nu[i]==-1){ nu[i]++; nu[i%n+1]--; v[k]=i; u[k++]=i%n+1; }else if(nu[i]==0){ continue; }else{ break; } } if(i!=n+1||nu[1]){ return false; } return true; } void clear(){ memset(u,0,sizeof(u)); memset(v,0,sizeof(v)); k=0; } int main() { int kase; scanf("%d",&kase); while(kase--){ scanf("%d",&n); long long allSum=0; for(int i=1;i<=n;i++){ scanf("%d",&num[i]); allSum+=num[i]; } if(allSum%n!=0){ printf("NO\n"); continue; } allSum/=n; bool can=true; for(int i=1;i<=n;i++){ num[i]-=allSum; s1[i]=s2[i]=num[i]; if(num[i]>2||num[i]<-2){ can=false; break; } } if(!can){ puts("NO"); continue; } bool noMove=true; for(int i=1;i<=n;i++){ if(num[i]!=0){ noMove=false; break; } } if(noMove){ printf("YES\n0\n"); continue; } clear(); s1[1]++; s1[2]--; u[k]=2; v[k++]=1; if(!give(s1)){ can=false; } if(!can){ clear(); s2[1]--; s2[2]++; v[k]=2; u[k++]=1; if(give(s2)){ can=true; }else{ clear(); } } if(!can&&give(num)){ can=true; } if(can){ puts("YES"); printf("%d\n",k); for(int i=0;i<k;i++){ printf("%d %d\n",u[i],v[i]); } }else{ puts("NO"); } } return 0; }