脚本宝典收集整理的这篇文章主要介绍了cf3,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
1.Codeforces Round #673 (Div. 2) D. Make Them Equal
大意:给出一个n个数的数组,你最多可以执行3*n次以下操作:选择三个整数 i,j,x,使a[ i ] = a[ i ] - x * i ,a[ j ] = a[ j ] + x * i 。操作完成后,能否使得这n个数相等 ?
题解:注意到 x 是可以任选的,那么当 i = 1 时,i*x 可以选择到任意整数,那么可以将 a[ 2 ] .... a[ n ] 的值全部集中到 a[ 1 ]上,再由 a[ 1 ]分配给它们。
#include<bITs/stdc++.h> using namespace std; #define ll long long const int maxn=3e4+50; int T,n,a[maxn],sum,t,ans1[maxn],ans2[maxn],ans3[maxn]; template<tyPEname T>void inline read(T &aa){ ll ff=1;char cc=getchar();aa=0; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') ff=-1,cc=getchar(); while(cc<='9'&&cc>='0') aa=aa*10+cc-48,cc=getchar(); aa*=ff; } int main(){ read(T); while(T--){ read(n); sum=0; t=0; for(int i=1;i<=n;i++){ read(a[i]); sum+=a[i]; } if(sum%n){ cout<<-1<<endl; continue; } int aver=sum/n;bool p=0; for(int i=2;i<=n;i++){ if(a[i]/i==0){ int x=i-a[i]; if(a[1]<x){ p=1; break; } ans1[++t]=1; ans2[t]=i; ans3[t]=x; a[1]-=x; ans1[++t]=i; ans2[t]=1; ans3[t]=1; a[1]+=i; a[i]=0; continue; } if(a[i]%i==0){ int x=a[i]/i; ans1[++t]=i; ans2[t]=1; ans3[t]=x; a[1]+=x*i; a[i]=0; continue; } int x=a[i]/i; x++; int xx=i*x-a[i]; if(a[1]<xx){ p=1; break; } ans1[++t]=1; ans2[t]=i; ans3[t]=xx; a[1]-=xx; ans1[++t]=i; ans2[t]=1; ans3[t]=x; a[1]+=x*i; a[i]=0; } if(p){ cout<<-1<<endl; continue; } for(int i=2;i<=n;i++){ int x=aver-a[i]; if(x==0) continue; ans1[++t]=1; ans2[t]=i; ans3[t]=x; } cout<<t<<endl; for(int i=1;i<=t;i++){ cout<<ans1[i]<<" "<<ans2[i]<<" "<<ans3[i]<<endl; } } return 0; }
以上是脚本宝典为你收集整理的cf3全部内容,希望文章能够帮你解决cf3所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。