链接
https://codeforces.com/contest/1478/problem/C
题意
假如数组 $a$ 长度为 $2n$，$a$ 中每个元素的相反数也在 $a$ 中。
记 $d_i=\sum_{j=1}^{2n}| a_i-a_j|$，已知数组 $d$，问是否有满足要求的数组 $a$。
思路
将数组 $d$ 从小到大排序，显然数组 $d$ 必须满足以下要求：
- $d_{2i}==d_{2i-1}$
- $d_{2i}!=d_{2_i-2}$
将数组 $d$ 中 $n$ 个不同的数从小到大排序，记这个数组为 $c$：
$c_i-c_{i-1}=\sum_{j=1}^{2n}| a_i-a_j|-\sum_{j=1}^{2n}| a_{i-1}-a_j|=2(i-1)(a_i-a_{i-1})(i\ge 2)$
判断 $a_i-a_{i-1}$ 是否是整数，如果都是整数，将 $c_n$ 化成 $c_n=2na_1+b$ 的形式，判断 $a_1$ 是否是正整数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=1e5+5;
int n;
vector<LL> a,b;
LL c[N];
bool check() {
sort(ALL(a));
for(int i=1;i<n<<1;i+=2) {
if(a[i]!=a[i-1]) return false;
b.PB(a[i]);
}
for(int i=1;i<n;i++) {
if(b[i-1]==b[i]||(b[i]-b[i-1])%(2*i)) return false;
c[i]=(b[i]-b[i-1])/(2*i);
}
LL sum=0,t=0;
for(int i=1;i<n;i++) t+=c[i],sum+=t;
t=0;
for(int i=n-1;i>=1;i--) t+=c[i],sum+=t;
sum+=n*t;
if(sum>=b[n-1]||(b[n-1]-sum)%(2*n)) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--) {
cin>>n;
a.clear();
b.clear();
for(int i=0;i<n<<1;i++) {
LL x;
cin>>x;
a.PB(x);
}
cout<<(check()?"YES":"NO")<<'\n';
}
return 0;
}
|