Codeforces Round #673 (Div. 2) D. Make Them Equal

D. Make Them Equal

這題的思維與之前一個cf題 CF658 C2. Prefix Flip 有些相似之處，都要求運算元小於某個值，思路都是找一箇中介。這題的中介就是a[1]，因為 a[1]%1==0 一定成立，那麼總是可以讓a[1]作為被減數，把a[1]的數加給其他任何位置。

（1）匯聚所有的數到a[1]。假設 $sum={\sum }_{i=1}^{n}a[i]$。
先想辦法把 a[i],i∈[2,n] 的所有數減到0，然後加給a[1]，但是在這個過程中有可能 a[i]%i!=0，那麼這時候先從a[1]這裡移數給a[i]讓它湊成i的倍數，然後再把湊成倍數的a[i]全部移回a[1]。
（2）將a[1]平均分配。現在a[1]=sum，只要把a[1]的值平均分配給每個位置即可。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int T,n,a[N];
struct node
{
    int a,b,c;
};
vector<node>ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        if(sum%n!=0){printf("-1\n");continue;}
        int ave=sum/n;
        ans.clear();
        int d;
        for(int i=2;i<=n;i++)
        {
            if(a[i]%i!=0) // 自己不能減小到0，還得a[1]變小加給它
            {
                int t=(int)(ceil(1.0*a[i]/i))*i; // a[i]需要變大到t
                d=t-a[i];
                a[1]-=d;
                a[i]+=d;
                if(d!=0)ans.push_back({1,i,d});
            }
            // a[i]可以把自己減小到0，全部加給a[1]
            d=a[i]/i;
            a[i]-=d;
            a[1]+=d;
            if(d!=0)ans.push_back({i,1,d});
        }
        for(int i=2;i<=n;i++)
            ans.push_back({1,i,ave});
        int sz=ans.size();
        printf("%d\n",sz);
        for(int i=0;i<sz;i++)
            printf("%d %d %d\n",ans[i].a,ans[i].b,ans[i].c);
    }
    return 0;
}
/*
100
7
2 1 -3 2 -4 5 -3
*/