CodeForces673 Div.2 D - Make Them Equal 思维，构造
题意
给定正数数组(a)，长度为(n)。
要求在(3n)次操作内使数组的值都相等。
操作描述如下：
任何操作结束后必须保证所有元素非负
[1.选择i,j,x.其中1leq i leq jleq n.0leq xle 10^9\
2.使得a_i -= x * i,a_j += x * i
]
[0 leq k leq 3n\
1leq 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() << '
';
for (int i = 0; i < res.size(); i++)
cout << res[i].i << ' ' << res[i].j << ' ' << res[i].x << '
';
}
int main() {
int T = readint();
while (T--) solve();
}