CodeForces673 Div.2 D - Make Them Equal 思维，构造

题意

给定正数数组\(a\)，长度为\(n\)。

要求在\(3n\)次操作内使数组的值都相等。

操作描述如下：

任何操作结束后必须保证所有元素非负

\[1.选择i,j,x.其中1\leq i \leq j\leq n.0\leq x\le 10^9\\ 2.使得a_i -= x * i,a_j += x * i \]

\[0 \leq k \leq 3n\\ 1\leq a_i \leq 10^5 \]

分析

贪心方案如下：

• 把\(2-n\)的数组变为\(i\)的倍数
• 把这些数加给\(a_1\)
• 让\(a_1\)分配给其他数

难点在于如何使每次操作后元素保持非负数，并且使得元素是\(i\)的倍数。

不妨令

\[a_1 = a_1 - (i - a_i \% i)\\ a_i = a_i + (i - a_i \% i) \]

容易通过数学归纳法证明这个构造方法。

代码

int a[10005];

struct S {
    int i, j;
    ll x;
    S(int _i, int _j, ll _x) {
        i = _i;
        j = _j;
        x = _x;
    }
};

void go(int x, int y, int val) {
    a[x] -= x * val;
    a[y] += x * val;
}

void solve() {
    int n = readint();
    ll sum = 0;
    for (int i = 1; i <= n; i++)
        a[i] = readint(), sum += a[i];
    if (sum % n) {
        puts("-1");
        return;
    }
    ll num = sum / n;
    vector<S> res;
    for (int i = 2; i <= n; i++) {
        if (a[i] % i) {
            res.push_back(S(1, i, i - a[i] % i));
            go(1, i, i - a[i] % i);
        }
        res.push_back(S(i, 1, a[i] / i));
        go(i, 1, a[i] / i);
    }
    for (int i = 2; i <= n; i++) {
        res.push_back(S(1, i, num));
        go(1, i, num);
    }
    cout << res.size() << '\n';
    for (int i = 0; i < res.size(); i++)
        cout << res[i].i << ' ' << res[i].j << ' ' << res[i].x << '\n';
}


int main() {
    int T = readint();
    while (T--) solve();
}