1478C Nezzar and Symmetric Array (构造)

末蓝、 2021-07-16 11:36 314阅读 0赞

[题目][Link 1]

思路：首先来看一下这个距离是怎么计算的  
\-4 -3 -2 -1 0 1 2 3 4 不难发现4到3和-3的距离和=2 \* 4 到-2 2到-1 1的距离和也都为2 \* 4，在此可以发现规律一个较大的数到两个较小的数的距离和等于其自身二倍。观察0 1 2 -1 -2…到4 -4的距离和为都为2\*4，又发现了一个规律一个绝对值较小的数和两个绝对值比它大的正负数的距离和=二倍大数的绝对值。

那么给出了d的序列，不难得出最大的那个di必然是最大的那个数和其他数的距离和，其对应的ai值为(di/2)/n,现在我们得到了最大的那个ai，那么我们现在要推出第二大的ai，其值=((第二大di)/2-最大ai)/(n-1)，依此类推，每求出一个ai判断其是否为整数、是否>0，若否则NO。另如果di为奇数或不是成对出现容易发现一定为NO。

看一个例子：

4  
40 56 48 40 80 56 80 48

首先d无奇数，每种d数量都为2

d由大到小排列为80 56 48 40

a1=(80/2)/4=10 符合整数且>0

a2=(56/2-10)/3=6 符合整数且>0

a3=(48/2-10-6)/2=4 符合整数且>0

a4=(40-10-6-4)=0不符合>0 NO

#include<iostream>
    #include<map>
    using namespace std;
    typedef long long ll;
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		ll n;cin >> n;
    		map<ll, ll,greater<ll>> ma;
    		int f = 0;
    		for (int i = 1;i <= 2 * n;i++)
    		{ 
    			ll a;cin >> a;ma[a]++;
    			if (a % 2 == 1)f = 1;
    		}
    		for (auto i = ma.begin();i != ma.end();i++)
    		{ 
    			if (i->second != 2)f = 1;
    		}
    		if (f)cout << "NO" << endl;
    		else
    		{ 
    			ll n = ma.size(), s = 0;
    			for (auto i = ma.begin();i != ma.end();i++)
    			{ 
    				if (i->first/2-s <= 0 || (i->first/2-s) % n != 0)
    				{ 
    					f = 1;break;
    				}
    				s += (i->first / 2 - s) / n;
    				n--;
    			}
    			if (f)cout << "NO" << endl;
    			else cout << "YES" << endl;
    		}
    	}
    }

[Link 1]: https://codeforces.ml/contest/1478/problem/C