C. Nezzar and Symmetric Array

题目大意:

定义 $a$ 数组为:对于每一个位置 $i(1\le i\le 2n)$,都能找到一个位置 $j(1\le j\le2n)$,使得 $a_i=-a_j$。($a_i$都是互不相同的整数)

定义 $d$ 数组为:$d_i=\sum_{j=1}^{2n} \left\vert a_i-a_j\right\vert$ 。

现在给你 $d$ 数组,请你判断是否有满足情况的 $a$ 数组。

解题思路:

既然涉及到了绝对值,那么我们可以将 $a$ 数组的 $2n$ 个点,看作数轴上的 $2n$ 个点,且因为题目特殊要求 $a_i=-a_j$,这些点在数轴上是对称的。

举个 $n=2$ 时的例子:

这$4$个点的对应的 $d_i$ 从左到右依次是:

$a+(a+2b)+(2a+2b)=4a+4b$

$a+b+2b+(a+2b)=2a+4b$

$(a+2b)+2b+b+a=2a+4b$

$(2a+2b)+(a+2b)+a=4a+4b$

发现了什么规律?

从这儿你肯定能发现:会有两个点对应的 $d_i$ 相等!

下面我们直接来看看一般情况

这次我们只讨论前 $n$ 个点。这 $n$ 个点的对应的 $d_i$ 从左到右依次是:

$d_1=c_1+(c_1+c_2)+...+(c_1+2c_2+...+2c_n)+(2c_1+2c_2+...+2c_n)=2nc_1+2nc_2+...+2nc_n$

$d_2=c_1+c_2+(c_2+c_3)+...+(2c_2+2c_3+...+2c_n)+(c_1+2c_2+...+2c_n)$

停!这个该怎么算呢?

我们发现,在这里只有最开始和最后出现了一次 $c_1$,剩下的还是照常,所以:

$d_2=c_1+c_2+(c_2+c_3)+...+(2nc_2+2nc_3+...+2nc_n)+(c_1+2c_2+...+2c_n)=2c_1+2nc_2+2nc_3+...+2nc_n$

那么如果接下来的按照刚刚的推,会得到:

$d_3=2c_1+4c_2+2nc_3+...+2nc_n$

$d_4=2c_1+4c_2+6c_3+2nc_4+...+2nc_n$

$...$

$d_n=2c_1+4c_2+6c_3+8c_4+...+(2n-2)c_{n-1}+2nc_n$

这里一定有:$\left\vert a_i\right\vert$越大,$d_i$越大

这里先定义:

f[n]=c[1]+c[2]+c[3]+...+c[n]
f[n-1]=c[2]+c[3]+..+c[n-1]+c[n]
...
f[2]=c[n-1]+c[n]
f[1]=c[n]

f[n]>f[n-1]>...>f[2]>f[1]

我们将 $d$ 数组排序,这样可以得到:

f[n]=d[2*n]/(n*2)
f[n-1]=(d[2*(n-1)]-2*f[n])/(2*(n-1))
f[n-2]=(d[2*(n-2)]-2*f[n]-2*f[n-1]/(2*(n-2)))
...
f[1]=(d[2]-2*f[n]-2*f[n-1]-...-2*f[3]-2*f[2])/(2*1)

如果 $f$ 数组中的数都为整数,且保证 $f_i>f_{i-1}$ 即可。

代码实现:[Code(洛谷炸了,先不贴云剪贴板)]()　时间复杂度O(Tn)

按理来说不应该会TLE吗。。。

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 200000+5;
long long T,n,d[MAXN];

bool check()
{
    for(int i=1;i<=n*2;i+=2)
        if(d[i]!=d[i+1])
            return true;
    return false;
}

int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);
        for(int i=1;i<=n*2;i++) scanf("%lld",&d[i]);
        sort(d+1,d+2*n+1);
        if(check()==true) {puts("NO");continue;}
        long long id=2*n,flag=1,num=2*n,sum=0,last=0;
//    id:  代表当前的位置。 
//    num: 应与id相等,即被除的数。 
//      sum: 记录当前f[1]+f[2]+...+f[i]的总和。
//    last:记录f[i-1]的值,用于与f[i]进行比较。 
        while(1)
        {
            if(id==0) break;//所有的f都满足要求 
            if((d[id]-2*sum)%num!=0 || (d[id]-2*sum)/num<=0)
                    {flag=0;break;}
            else 
            {
                if(last!=0 && last<=((d[id]-2*sum)/num))
                    {flag=0;break;}
                last=((d[id]-2*sum)/num); 
                sum+=((d[id]-2*sum)/num),id-=2,num-=2;
            }
        }
        if(flag==1) puts("YES");
        else puts("NO");
    }
    return 0;
}