只過了Pretest，可能有誤，歡迎批評指正

題面：https://codeforces.com/contest/1478/problem/C#

題意：

a陣列有2n個元素，兩兩不同，且每個數和它的絕對值同時出現，如[-3,3,-1,1]，

根據公式 d i = ∑ j = 1 2 n ∣ a i ? a j ∣ d_{i}=\sum_{j=1}^{2 n}\left|a_{i}-a_{j}\right| di?=∑j=12n?∣ai??aj?∣ 求得d陣列，即：d陣列中每個元素，為a陣列相應元素和其他所有元素絕對值的和，

已知d陣列，求是否存在合法的a陣列，

思路：

顯然，d陣列和a陣列中，元素的順序沒什么卵用

假設a陣列從大到小排好了序，只考慮a陣列中的正數（也就是前n個）

容易發現

d i = ∑ j = 1 n m a x ( 2 a i , 2 a j ) d_i= \sum_{j=1}^{n} max(2a_i,2a_j) di?=∑j=1n?max(2ai?,2aj?)

看圖！

舉個例子

例如a=[6,3,1,-1,-3,-6]

d 1 = 2 ? 6 + 2 ? 6 + 2 ? 6 = 36 d_1=2*6+2*6+2*6=36 d1?=2?6+2?6+2?6=36，因為 m a x ( 6 , 6 ) = 6 , m a x ( 6 , 3 ) = 6 , m a x ( 6 , 1 ) = 6 max(6,6)=6, max(6,3)=6, max(6,1)=6 max(6,6)=6,max(6,3)=6,max(6,1)=6

d 2 = 2 ? 6 + 2 ? 3 + 2 ? 3 = 24 d_2=2*6+2*3+2*3=24 d2?=2?6+2?3+2?3=24，因為 m a x ( 3 , 6 ) = 6 , m a x ( 3 , 3 ) = 3 , m a x ( 3 , 1 ) = 3 max(3,6)=6, max(3,3)=3, max(3,1)=3 max(3,6)=6,max(3,3)=3,max(3,1)=3

d 3 = 2 ? 6 + 2 ? 3 + 2 ? 1 = 20 d_3=2*6+2*3+2*1=20 d3?=2?6+2?3+2?1=20，因為 m a x ( 1 , 6 ) = 6 , m a x ( 1 , 3 ) = 3 , m a x ( 1 , 1 ) = 1 max(1,6)=6, max(1,3)=3, max(1,1)=1 max(1,6)=6,max(1,3)=3,max(1,1)=1

所以d=[36,24,20,20,24,36]

由于順序沒卵用，因此，若d陣列是這一坨數，不管順序如何，都一定YES

d有什么性質呢？

假設a陣列從大到小排列，假設a陣列從大到小排列，假設a陣列從大到小排列，重要的事情說三遍！后文默認a是從大到小排好序的，d陣列根據公式推出：

首先， d 1 = 2 n a 1 d_1=2na_1 d1?=2na1?，因為 a 1 a_1 a1?一定是a陣列中最大的數，根據上述公式， d 1 = 2 a 1 + 2 a 1 + ? + 2 a 1 = 2 n a 1 d_1=2a_1+2a_1+\cdots+2a_1=2na_1 d1?=2a1?+2a1?+?+2a1?=2na1?，

只有 a 1 > a 2 a_1>a_2 a1?>a2?，而且 a 3 ? a n a_3\cdots a_n a3??an?均小于 a 2 a_2 a2?，因此 d 2 = 2 a 1 + 2 a 2 + 2 a 2 + ? + 2 a 2 = 2 a 1 + 2 ( n ? 1 ) a 2 d_2=2a_1+2a_2+2a_2+\cdots+2a_2=2a_1+2(n-1)a_2 d2?=2a1?+2a2?+2a2?+?+2a2?=2a1?+2(n?1)a2?

同理可得 d 3 = 2 a 1 + 2 a 2 + 2 ( n ? 2 ) a 3 d_3=2a_1+2a_2+2(n-2)a_3 d3?=2a1?+2a2?+2(n?2)a3?

d k = 2 a 1 + 2 a 2 + ? + 2 a k ? 1 + 2 ( n ? k + 1 ) a k d_k=2a_1+2a_2+ \cdots+2a_{k-1}+2(n-k+1)a_k dk?=2a1?+2a2?+?+2ak?1?+2(n?k+1)ak?

對于a的負數部分，其對應的d和正數部分對稱出現，即 a 1 = ? a 2 n , d 1 = d 2 n ; a 2 = ? a 2 n ? 1 , d 2 = d 2 n ? 1 a_1=-a_{2n}, d_1=d_{2n}; a_2=-a_{2n-1}, d_2=d_{2n-1} a1?=?a2n?,d1?=d2n?;a2?=?a2n?1?,d2?=d2n?1?，也就是說，d陣列中的數必須成對出現，由于上面的公式每一項都乘了2，因此d陣列中的數必須都是偶數，

這一頓操作猛如虎，有什么用呢？別急！馬上出來了！

那么怎么樣的一坨數才算YES呢？

首先，都是偶數，可以在輸入時就進行判斷，

其次，必須成對出現，從大到小排序后，必須滿足“對于任意的奇數i（ 1 ≤ i ≤ 2 n ? 1 1\leq i\leq 2n-1 1≤i≤2n?1），有 d [ i ] = = d [ i + 1 ] d[i]==d[i+1] d[i]==d[i+1]，判斷的程序可以同時去重，以便和上述的a陣列對應，如d1對應a1，

然后！！！！！

假設d陣列已經從大到小排列并去重（相同的兩個數只保留一個）

由于 d 1 = 2 n a 1 d_1=2na_1 d1?=2na1?，所以必須有 d 1 % 2 ( n ? 1 ) = = 0 d_1\%2(n-1)==0 d1?%2(n?1)==0， a 1 = d 1 / 2 n a_1=d_1/2n a1?=d1?/2n

由于 d 2 = 2 a 1 + 2 ( n ? 1 ) a 2 d_2=2a_1+2(n-1)a_2 d2?=2a1?+2(n?1)a2?，所以必須有 ( d 2 ? 2 a 1 ) % 2 ( n ? 1 ) = = 0 (d_2-2a_1)\%2(n-1)==0 (d2??2a1?)%2(n?1)==0， a 2 = ( d 2 ? 2 a 1 ) / 2 ( n ? 1 ) a_2=(d_2-2a_1)/2(n-1) a2?=(d2??2a1?)/2(n?1)

由于 d 3 = 2 a 1 + 2 a 2 + 2 ( n ? 2 ) a 3 d_3=2a_1+2a_2+2(n-2)a_3 d3?=2a1?+2a2?+2(n?2)a3?，所以必須有 ( d 3 ? 2 a 1 ? 2 a 2 ) % 2 ( n ? 2 ) = = 0 (d_3-2a_1-2a_2)\%2(n-2)==0 (d3??2a1??2a2?)%2(n?2)==0

對于任意的 2 ≤ k ≤ n 2\leq k\leq n 2≤k≤n，有 ( d k ? 2 a 1 ? 2 a 2 ? ? ? 2 a k ? 1 ) % 2 ( n ? k + 1 ) = = 0 (d_k-2a_1-2a_2-\cdots-2a_{k-1})\%2(n-k+1)==0 (dk??2a1??2a2????2ak?1?)%2(n?k+1)==0

每次“減去的數”多了一個 2 a i 2a_i 2ai?，因此可以用一個變數維護，如果其中任何一個不為0，則輸出NO

還有！！！！！

我們假設a陣列是單調遞減且不重復的，前n個數是正數！！！！如果算到哪一步， d k ? 2 a 1 ? 2 a 2 ? ? 2 a k ? 1 ≤ 0 d_k-2a_1-2a_2-\cdots2a_{k-1}\leq0 dk??2a1??2a2???2ak?1?≤0了，那就沒了！！！！如果算出哪一步的 a i a_i ai?大于上一步的 a i ? 1 a_{i-1} ai?1?，也不可以！！！！！

C++代碼

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll d[200005], n;
int main()
{
    ios::sync_with_stdio(false);
    int t; cin>>t;
    while(t--)
    {
        cin>>n;
        for(ll i=1;i<=n*2;i++)
            cin>>d[i]; 
        sort(d+1,d+2*n+1,[](ll x,ll y)->bool{return x>y;}); //從大到小排序

        bool flag = true;
        for(ll i=1;i<=n*2-1;i+=2) //我沒有去重！！！只判斷了
        {
            if(d[i]%2 || d[i]!=d[i+1]) flag = false; //必須兩兩一組出現，而且得是偶數
        }
        if(d[1]%(n*2)!=0) flag = false;

        ll pre = d[1]/n, cnt = 2*n, last = d[1]/n; //已經加的，剩余個數，上一個a[i]的二倍
        for(ll i=3;i<=2*n-1 && flag;i+=2)
        {
            cnt-=2; //剩余數字個數-2
            d[i] -= pre;
            //cout<<a[i]<<endl;
            flag &= (d[i]>0);
            flag &= (d[i]%cnt==0);
            pre += d[i]/cnt*2; //已經求過的數之和
            ll now = d[i]/cnt*2; //這一個a[i]的二倍
            flag &= (now<last); //a陣列必須嚴格單調遞減
            //cout<<last<<" "<<now<<endl;
            last = now;
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}