Codeforce 1416 B. Make Them Equal 解析(思維)

今天我們來看看CF1416B
題目連結

題目
略，請直接看原題。

前言

實在很難想像我要多久以後才有辦法獨立快速地想出這題的解法。

想法

首先會發現如果能夠先把數字都集中到第$1$個元素的話，那麼我們可以輕鬆地分配給所有元素。(我們可以透過元素總和獲得最後每個元素應該要是多少)
然而上面所說的把數字集中到第一個元素，指的是先把所有其他元素都減成$0$，也就是說，如果$a[i]$一開始並不能被$i$整除，我們要先把$a[i]$從$a[1]$分配$i-a[i]%i$過去，而注意到$i-a[i]%i<i$，又因為有$a[i]\ge1\forall i$，這樣只要能夠確定，只要元素總和可以被$n$整除，就一定有解答。

程式碼:

const int _n=1e4+10;  
int t,n,a[_n],fin,cnt;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    fin=0;cin>>n;rep(i,1,n+1){cin>>a[i];fin+=a[i];}if(fin%n){cout<<-1<<'\n';goto A;}  
    fin/=n;cnt=2*(n-1);rep(i,2,n+1)if(a[i]%i)cnt++; cout<<cnt<<'\n';  
    rep(i,2,n+1){  
      if(a[i]%i==0){cout<<i<<' '<<1<<' '<<a[i]/i<<'\n';a[1]+=a[i],a[i]=0;}  
      else{  
        cout<<1<<' '<<i<<' '<<i-a[i]%i<<'\n';  
        a[1]-=i-a[i]%i,a[i]+=i-a[i]%i;  
        cout<<i<<' '<<1<<' '<<a[i]/i<<'\n';  
        a[1]+=a[i],a[i]=0;  
      }  
    }rep(i,2,n+1){cout<<1<<' '<<i<<' '<<fin<<'\n';}  
    A:;  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission