思路:
由于每个数正负成对出现,不妨设x为正,对于x与每个数对(不妨设为y,-y)的绝对值差为|x - y| + |x + y|,则-x与每个数对的绝对值差为|-x - y| + |-x + y| = |x + y| + |x - y|,故d数组中每个数都应成对出现;
对于|x + y| + |x - y|
当x > y时为2x;
当y > x时为2y;
即|x + y| + |x - y| = 2 * max(x,y),故d数组所有数都应为偶数;
因此di = $\sum_{j=1}^{2n} max(abs(a[i]),abs(a[j]))$ ,由于每个a[j]成对出现,所以只需存下所有正项乘以2即可;
假设最大的数a[i]为max,则d[i] = max * 2 * n,max = d[i] / 2 / n;
假设次大数a[j]为max2除了与最大数max求绝对值差和时加的是2*max,其他都为次大数max2,所有d[j] = max2 * 2 * (n - 1) + max * 2,max2 = (d[j] - max * 2) / 2 / (n - k);
然后从大到小一直向前推即可,一边推一边记录已经推出的的数的总和,推的过程有矛盾就输出NO
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5+5;
int mod = 1e9 +7;
int n,m,k;
map<int,int> mp;
map<int,bool> vis;
void solve(){
cin >> n;
mp.clear();
vis.clear();
for(int i = 0 ; i < 2 * n ; ++i){
cin >> k;
//存相反数实现从大到小排序
mp[-k]++;
}
//记录目前求出的数和,以及求出的数目
int cur = 0,k = 0;
for(auto it : mp){
int x = -it.first,y = it.second;
//如果有奇数或者出现次数为奇数,或者大于2次
if(x % 2 || y % 2 || y > 2){
cout << "NO" << endl;
return;
}
int t = (x - cur * 2) / 2;
int d = n - k;
//判断是否可以整除,(这里被卡了两次呜呜呜
if(t % d){
cout << "NO" << endl;
return;
}
t /= d;
//判断t是否重复,或者小于0
if(vis.count(t) || t <= 0){
cout << "NO" << endl;
return;
}
//记录并更新总和
vis[t] = true;
cur += t;
k++;
}
//未发现矛盾则输出正确
cout << "YES" << endl;
}
signed main(){
IOS;
int tt;
cin >> tt;
while(tt--)
solve();
return 0;
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/