2021-03-21_nezzar and

Nezzar and Symmetric Array

题目来源c’f
题目描述
C. 内扎尔和对称阵列
每次测试的时间限制2秒
每个测试的内存限制512兆字节
输入标准输入
输出标准输出
很久以前，有一个对称的阵列 a1，a2,…,a2n 由 2n 不同的整数组成。如果每个整数 1≤i ≤2n，则阵列 a1，a2,…,a2n 称为对称，则存在一个整数 1≤j ≤2n，以便 ai=aj。

对于每个整数 1≤i ≤2n，Nezzar 在 a.∑2nj=1 |ai-aj |中写下了一个等于从 ai 到所有整数的绝对差异的总和的整数。

现在一百万年过去了， 内扎尔几乎不记得阵列 d， 完全忘记了一个。Nezzar 想知道是否存在由生成阵列 d 的 2n 不同整数组成的对称阵列。

输入
第一行包含一个整数t（1≤t≤10⁵）——测试案例的数量。

每个测试案例的第一行包含一个整数 n （1≤n ≤10⁵）。

每个测试案例的第二行包含 2n 整数 d1、d2 ,…,d2n （0≤di ≤10¹²）。

保证所有测试案例的总和不超过 105。

输出
对于每个测试案例，如果存在可能的阵列 a，请在单行中打印"是"。否则，打印"否"。

您可以在任何情况下打印字母（上部或下部）。

例子
输入复制
6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210
输出复制
YES
NO
NO
NO
NO
YES
注意
在第一个测试案例中，a=[1，3，-1，-3] 是生成阵列 d=[8，12，8，12] 的可能对称阵列。

在第二个测试案例中，可以显示没有由能够生成阵列 d 的不同整数组成的对称阵列。
解题思路
1.原数组包括N个整数和N个负数，绝对值相同一正一负与其他数字的差的绝对值之和一定是相同的，那么d数组中的值一定是成对出现；
2.如果N个整数组成一个数组x[n],数组内部按从小到大的顺序排列，可以得到以下规律(先将d数组从大到小排列好）x数组都是求的正数
x[1]=d[1] / (2n);
x[2]=(d[3] - 2(x[1])) / (2(n-1));
x[3]=(d[5] - 2x[1] -2x[2] ) / (2(n-2));
…
x[n]=(d[2n-1] -2x[1] - 2x[2] -…-2x[n-1] ) / 2;
3.注意是不同的整数，而且必须可以被整除
4 .求的过程中都是正数

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
long long n,a[200005],x[100005],h;
bool cmp(long long x,long long y)
{
	return x>y;
} 
int check()
{
	for(int i=1;i<2*n;i+=2)
	{
		if(a[i]!=a[i+1]||a[i]%2||a[i+1]==a[i+2])
			return 1;
	}
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;	
		int flag=0;
		for(int i=1;i<=2*n;i++)
		{
			cin>>a[i];
		}
		sort(a+1,a+2*n+1,cmp);								
		if(check()) 
			cout<<"NO"<<endl;
		else
		{	
			long long aa,sum=0,flag=1;
			for(int i=2;i<=2*n;i+=2)
			{
				if(((a[i]-sum)%(2*(n-i/2+1))!=0)||((a[i]-sum)<=0))
				{
					flag=0;
					cout<<"NO"<<endl;
					break;
				}
				aa=(a[i]-sum)/2/(n-i/2+1);
				sum+=aa*2;		
			}
			if(flag)
				cout<<"YES"<<endl;
		}
	
	}
		return 0;	
}
 
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