题目链接：Nezzar and Symmetric Array
? 有一个数组 \(a\) ，共有 \(2n\) 个整数，且每个数互不相等，对于每个数 \(a_i\) 都能在这个数组里找到一个数 \(a_j\) 使得 \(a_i\)和 \(a_j\) 互为相反数，即\(a_i=-a_j\) 。
? 除此之外还有一个数组 \(d\) ，有 \(2n\) 个整数，每个整数 \(d_i\) 代表 \(a_i\) 与 \(a\) 中每个元素之差的绝对值之和。
? 给你数组 \(d\) ，问你该数组 \(d\) 对应的数组 \(a\) 是否存在。
? \(a\) 中每个数互不相同，且每个数都能在 \(a\) 中找到自身的相反数，也就是说数组 \(a\) 中不包含0，若包含0则 \(a\) 中的数字个数只能是奇数。
? 不仅如此，我们还能推出 $ a$ 中含有 \(n\) 个正数和 \(n\) 个负数，且这些正数和负数在数轴上关于0点对称，比如：
? 
?
? 假设 \(a_i\) 和 \(a_j\) 是一对相反数，在数轴上显然 \(a_i\) 到0点的距离和 \(a_j\) 到0点的距离相等，于是，不难得到 \(a_i\) 到 \(a_j\) 的距离是偶数。
? 两数之差的绝对值在数轴上相当于两点间的距离，所以， \(d_i\) 等于\(a_i\) 与 \(a\) 中其他元素的距离之和，对于 \(d_i\) 的相反数，两者间的距离自然是偶数，对于 \(a\) 中其他元素 \(a_j\) ，假设 \(a_k\) 是 \(a_j\) 的相反数，则 \(a_i\) 与 \(a_j\) 的距离加上 \(a_i\)与 \(a_k\) 的距离也是偶数，偶数相加必然也是偶数。
? 于是我们得到1第个对数组 \(d\) 的要求：\(d\) 中每个数均为偶数。
? 经过观察，我们可以发现对于一对相反数 \(a_i\) 和 \(a_j\) ，其 \(d_i\) 和 \(d_j\) 相等，又因为 \(a\) 中每个数互不相等，则可得到第2个对数组 \(d\) 的要求：\(d\) 中每个数的出现次数必定为两次。
? 通过观察（玄学）发现， \(d_i\) 越小，对应的 \(a_i\) 越靠近0点， \(d_i\) 越大，对应的 \(a_i\) 越远离0点。
? 现在假设数组 \(a\) 已经按照升序排序，个人习惯，下标从1开始，其中 \(a_1\) 到 \(a_n\) 在数轴负半轴， \(a_{n+1}\)到 \(a_{2n}\) 在正半轴，对于正半轴上的 \(a_i\) 和\(a_{i+1}\) ，对应的\(d_i\) 和 \(d_{i+1}\) 如图：
红线长度之和是 \(d_i\) ， 蓝线长度之和是 \(d_{i+1}\)
? 可以发现，在两绿线两侧的红线长度之和与蓝线长度之和相等，尽在两绿线之间的红线长度和与蓝线长度和不等，于是，可以推出 \(d_{i+1}\) 与 \(d_i\) 的差是 \(a_{i-1}\) 到 \(a_i\) 距离的整数倍。
? 经计算可以得出 \(d_{i+1}-d_i=2i(a_{i+1}-a_i)\) ，注意此处 \(i\) 在正半轴上。
? 我们可以通过以上方法求出正半轴上所有 \(a_i\) 与 \(a_{i+1}\) 的相对位置，因负半轴和正半轴对称，求出正半轴也相当于求出了负半轴。
? 但仅求出相对距离还不够，我们还要求出 \(a\) 中每个数的绝对位置，只需求出 \(a\) 中一个数在数轴上的绝对位置，其他数的绝对位置则可由之前算出的相对位置求出。
? 考虑在正半轴上的 \(a_{n+1}\) 和在负半轴上的 \(a_n\) ，两数互为相反数，关于0点对称，那么只要求出 \(a_n\) 到 \(a_{n+1}\) 的距离，就可以算出 \(a_{n+1}\) 或 \(a_n\) 到0点的距离，也就是两数的绝对位置也可以确定。
? 现在考虑如何求 \(a_{n+1}-a_n\) ，对于上面的 \(d_{i+1}-d_i=2i(a_{i+1}-a_i)\) ，此处并不适用，但我们已经知道了正半轴以及负半轴上相邻两个数的的相对位置，则可以通过这些信息推算出 \(a_{n+1}-a_n\) 的值。
? \(d_{n+1}\) 在数轴上表示如图：
? 图中了绿线部分，可以用之前求出的相对位置算出，我们发现，\(d_{n+1}\) 减去这些绿线的长度，剩下的值是 \(a_{n+1}-a_n\) 的 \(n\) 倍，由此，我们就能算出 \(a_{n+1}\) 的绝对位置。
? 因为 \(a_n\) 和 \(a_{n+1}\) 关于0点对称，则 \(a_{n+1}-a_n\) 必定为偶数且大于0，又因为 \(a_{n+1}\) 在正半轴上，所以要求 \(a_{n+1}\) 大于0，所以可以得到两个要求：
整理一下判断 \(a\) 是否存在的依据：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[200000+10],d1[200000+10];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll t,n;
cin>>t;
while(t--)
{
ll flag=0,tot=1;
map <ll,ll> mp;
cin>>n;
n<<=1;
for(ll i=1;i<=n;i++)
{
cin>>d[i];
if(d[i]&1LL)
{
flag=1;
}
mp[d[i]]++;
}
if(flag)
{
cout<<"NO"<<"\n";
continue;
}
n>>=1;
for(auto it=mp.begin();it!=mp.end();it++)
{
d[tot++]=it->first;
if(it->second!=2)
{
flag=1;
break;
}
}
if(flag)
{
cout<<"NO"<<"\n";
continue;
}
sort(d+1,d+1+n);
tot=1;
for(ll i=1;i<=n-1;i++)
{
ll num=d[i+1]-d[i];
if(num&1||num%(2LL*i)!=0)
{
flag=1;
break;
}
d1[i]=num/(2LL*i);
}
if(flag)
{
cout<<"NO"<<"\n";
continue;
}
ll cnt=2,sum=0;
for(ll i=n-1;i>=1;i--,cnt+=2)
{
d[1]-=cnt*d1[i];
if(d[1]<=0)
{
flag=1;
break;
}
}
if(d[1]%n!=0)
flag=1;
else
d[1]/=n;
if(d[1]<=0||d[1]&1)
flag=1;
if(flag)
cout<<"NO"<<"\n";
else
cout<<"YES"<<"\n";
}
return 0;
}
【CF1478C】 Nezzar and Symmetric Array
原文：https://www.cnblogs.com/zjl4785/p/14377079.html