https://codeforces.com/contest/1417/problem/D
思路：觀察一下樣例可以知道能構造出來的最后會變成平均值，
想著題目3*n，所以可以考慮掃三次序列，最后一次應該是把通過一個數把全部數字變成平均數，那么前兩次應該是收集到一個數字上，
構造想著方便那么用i==1去構造，但是發現題目的ai只能是減，ai減到負數之類的就不好搞了，所以要嘗試把后面的數都加到ai，但是直接加沒法加，要使得a1加的話后面只能是減，發現后面的數要減完只能是i的倍數，所以第一次要把i=2~n全部變成i的倍數，這個理論上是可以成立的，（雖然不是很懂要怎么去證明），第一次之后再把后面的數都放到a1去，最后由a1平均分配，
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL a[maxn];
void oper(LL i,LL j,LL x)
{
a[i]-=i*x;
a[j]+=i*x;
cout<<i<<" "<<j<<" "<<x<<endl;
}
void solve()
{
LL n;cin>>n;LL sum=0;
for(LL i=1;i<=n;i++) cin>>a[i],sum+=a[i];
if(sum%n) {
cout<<"-1"<<endl;return;
}
cout<<3*(n-1)<<endl;
for(LL i=2;i<=n;i++)
{
oper(1,i,(i-a[i]%i)%i);
oper(i,1,a[i]/i);
}
for(LL i=2;i<=n;i++)
{
oper(1,i,sum/n);
}
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/142292.html
標籤：其他