题解 CF1416B 【Make Them Equal】

AFOier · 2020-11-13 08:12:35 · 题解

注意到a[i]减的数与a[j]加的数相同，所以序列之和不变.

取平均值，若不为整数，则输出-1.

因为i=1可以最细化每个数的变化，故考虑所有操作围绕a[1]进行.

有一种方案为（以下i∈[2,n]）：

1.将a[i]变为i的倍数.

2.将a[i]变为0.

对于每个i重复操作1,2（这两个操作可以使a[1]+=a[i],a[i]=0）.

3.将a[1]的值平均分给每个a[i].

这样操作次数为3(n-1)，符合要求.

考虑正确性：

对于1操作，因为a[i] \geqslant 1，所以在处理到第i个数时，a[1]=sum[1,i-1] \geqslant i-1.

又因为a[i] \bmod i \leqslant i-1,所以将a[i]变为i的倍数时，a[1]一定非负.

其余操作的显然不会使序列中出现负数.

#include <bits/stdc++.h>
using namespace std;
int a[100011];
int n, sum;
void solve() {
    scanf("%d", &n); sum = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    if(sum % n) {
        printf("-1\n");
        return;
    }
    sum /= n;
    cout << 3 * (n-1) << endl;
    for(int i = 2; i <= n; i++) {
        int x = a[i] % i;
        cout << 1 << " " << i << " " << (i - x) % i << endl;
        a[1] -= (i - x) % i; a[i] += (i - x) % i;
        cout << i << " " << 1 << " " << a[i] / i << endl;
        a[1] += a[i]; a[i] = 0; 
    }
    for(int i = 2; i <= n; i++) {
        cout << 1 << " " << i << " " << sum << endl;
        a[1] -= sum; a[i] += sum;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}