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

View Code