B. Make Them Equal 解析(思維)

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

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

題目
略，請直接看原題。

前言

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

@copyright petjelinux 版權所有
觀看更多正版原始文章請至petjelinux的blog

想法

首先會發現如果能夠先把數字都集中到第(1)個元素的話，那麼我們可以輕鬆地分配給所有元素。(我們可以透過元素總和獲得最後每個元素應該要是多少)
然而上面所說的把數字集中到第一個元素，指的是先把所有其他元素都減成(0)，也就是說，如果(a[i])一開始並不能被(i)整除，我們要先把(a[i])從(a[1])分配(i-a[i]\%i)過去，而注意到(i-a[i]\%i<i)，又因為有(a[i]ge1forall 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<<'
';goto A;}
    fin/=n;cnt=2*(n-1);rep(i,2,n+1)if(a[i]%i)cnt++; cout<<cnt<<'
';
    rep(i,2,n+1){
      if(a[i]%i==0){cout<<i<<' '<<1<<' '<<a[i]/i<<'
';a[1]+=a[i],a[i]=0;}
      else{
        cout<<1<<' '<<i<<' '<<i-a[i]%i<<'
';
        a[1]-=i-a[i]%i,a[i]+=i-a[i]%i;
        cout<<i<<' '<<1<<' '<<a[i]/i<<'
';
        a[1]+=a[i],a[i]=0;
      }
    }rep(i,2,n+1){cout<<1<<' '<<i<<' '<<fin<<'
';}
    A:;
  }
  return 0;
}

標頭、模板請點Submission看
Submission