题目链接
翻译
给你 (2n) 个数字, 每个数字各不相同,如果 (a[i]) 存在的话,那么 (-a[i]) 也会存在于这个数组中。
定义 (d_i) 为 (a_i) 和所有数字的差的绝对值之和。
现在告诉你 (d_i),让你还原出来原始的 (a_i)。
题解
我们假设 (a_1,a_2,a_3...a_n) 分别为最大的 (n) 个正数(会对应 (n) 个负数),且从大到小排序。
那么,(a_1) 对应的 (d_i) 的值中绝对值的形式就可以去掉了,因为不管减还是加上某个数都是正的了。
(a1+x),(a1-x)...
可以想见最后的 (d_i) 的值就是 (2*n) 个 (a_1)。
然后考虑 (a_2)。
会发现除了 (|a_2-a_1|) 是负数,会变为 (-a_2+a_1) 之外,其他的项都是正数,绝对值可以去掉。
而这可以和 (a_2-(-a_1)) 即 (a_2+a_1) 抵消掉 (a_2)
那么 (d_2) 的值就为 (2*a_1+(n-2)*a_2), 发现了吧,以此类推 (d_3=2*a_1+2*a_2+(n-4)*a_3)。
并且 (d) 的值也是单调递减的。根据能否整除,以及 (a_1) 到 (a_n) 都是正数且下降这些性质验证一下算出来的 (a_i) 是不是对的就好了。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5;
int T,n;
LL d[N + 10],a[N+10];
int main() {
#ifdef LOCAL_DEFINE
freopen("in.txt", "r", stdin);
#endif // LOCAL_DEFINE
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
cin >> d[i];
}
sort(d + 1, d + 1 + 2*n);
bool check = true;
for (int i = 2; i <= 2 * n; i += 2) {
if (d[i] != d[i - 1]) {
check = false;
}
}
reverse(d + 1, d + 1 + 2*n);
int cur = 2*n;
LL temp = 0;
for (int i = 1; i <= n; i++) {
int j = 2 * i;
d[j] -= temp;
if (d[j] % cur != 0) {
check = false;
}
a[i] = d[j] / cur;
if (a[i] <= 0) {
check = false;
}
if (i > 1 && a[i] >= a[i - 1]) {
check = false;
}
temp += 2 * a[i];
cur -= 2;
}
if (!check) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
}
}
return 0;
}