codeforce 1474C C. Array Destruction 找规律打表 C

https://codeforces.com/contest/1474/problem/C

You found a useless array

It could have been an easy task, but it turned out that you should follow some rules:

In the beginning, you select any positive integer
Then you do the following operation
- select two elements of array with sum equals
- remove them from

For example, if initially

Note, that you choose

Determine how should you behave to throw out all elements of

Input

The first line contains a single integer

The first line of each test case contains the single integer

The second line of each test case contains

It is guaranteed that the total sum of

Output

For each test case in the first line print YES if it is possible to throw out all elements of the array and NO otherwise.

If it is possible to throw out all elements, print the initial value of

Example

input

Copy

4
2
3 5 1 2
3
1 1 8 8 64 64
2
1 1 2 4
5
1 2 3 4 5 6 7 14 3 11

output

Copy

YES
6
1 5
2 3
NO
NO
YES
21
14 7
3 11
5 6
2 4
3 1

Note

The first test case was described in the statement.

In the second and third test cases, we can show that it is impossible to throw out all elements of array

题意是要求从整个数组中每次选出来俩数删掉，然后保留最大值，使得下一次删除的两个数之和是这个最大值。

由题意可以画出来一个二叉树。

会发现所有的数中有一个数是无效的，也就是二叉树的顶点的右分支

注意到n是1000，所以肯定要进行一次循环把这个数进行选出来

再注意到排除这个数之后，二叉树的左分支每次只能选择当前数组最大的进行

那么我们可以从后往前进行扫描，每次删除两个数，如果无法删除，则无效，删除的过程可以使用lower_bound加快速度

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <iostream>
#include <time.h>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <string.h>
#include <bitset>
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123
");
#define pn printf("
");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d
",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define ll long long
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define eps 1e-13
#define zero(x) (((x) > 0? (x):(-x)) < eps)
using namespace std;
int a[4005];
int main(){
    int t;
    s(t)

    while(t --){
        int n;
        s(n)
        n *= 2;
        for(int i = 0; i < n; i ++){
            s(a[i])
        }
        sort(a,a+n);
        vector<int> b(2000);
        map<int,int> m;
        m.clear();
        int x = -1;
        for(int i = 0; i < n-1; i ++){
            int maxi = a[i] + a[n-1];
            //p(a[i]) pk p(maxi) pn
            b.clear();
            m.clear();
            //p(maxi) pn
            for(int j = n-1;  j >= 0; j --){
                if(m[a[j]] == 0 && maxi-a[j] <= a[j]){
                    m[maxi-a[j]] ++;
                    b.push_back(a[j]);
                    b.push_back(maxi-a[j]);
                    //p(a[j]) pk p(maxi-a[j]) pk p123 pn
                    maxi = a[j];
                }else if(m[a[j]] > 0){
                    m[a[j]] --;
                }else{
                    goto l;
                }
            }
            //b.push_back(a[i]);
            sort(b.begin(),b.end());
            for(int j = 0; j < n; j ++){
                //p(b[j]) pk p(a[j]) pn
                if(b[j] != a[j]){
                    goto l;
                }
            }
            //pn pn pn pn
            x = i;
            l:0;
        }
        if(x == -1){
            puts("NO");
        }else{
            puts("YES");
            p(a[x]+a[n-1]) pn
            int maxi = a[x]+a[n-1];
            m.clear();
            for(int j = n-1;  j >= 0; j --){
                if(m[a[j]] == 0 && maxi-a[j] <= a[j]){
                    m[maxi-a[j]] ++;
                    p(a[j]) pk p(maxi-a[j]) pn
                    maxi = a[j];
                }else if(m[a[j]] > 0){
                    m[a[j]] --;
                }
            }
        }
















        /*
        int flag = 0;
        //a[i]������
        int i = 0;
        int x[3000];
        for(i = 0; i < n-1; i ++){
            re(x,0);
            x[i] = 1;
            for(int j = n-1; j >= 0; j --){
                if(x[j] == 0){//ûʹ�ù� ����
                    x[j] = 1;
                    for(int k = j-1; k >= 0; k --){//�Ҵδ��
                        if(x[k] == 0){
                            x[k] = 1;
                            int y = lower_bound(a,a+n,a[j]-a[k])-a;
                            for(int ii = y; ii < n; ii ++){
                                if(a[ii] != a[j]-a[k]){
                                    goto l;
                                }
                                if(x[ii] == 0){
                                    x[ii] = 1;
                                    goto l0;
                                }
                            }
                        }
                    }
                }
                l0:0;
            }
            for(int j = 0; j < n; j ++){
                if(x[j] == 0){
                    goto l;
                }
            }
            flag = 1;
            break;
            l:0;
        }
        if(flag == 1){
            puts("YES");
            p(a[n-1]) pk p(a[i]) pn
            p(a[n-1]+a[i]) pn
        }else{
            puts("NO");
        }*/
    }
    return 0;
}

codeforce 1474C C. Array Destruction 找规律 打表 C

相关推荐

codeforce 1474C C. Array Destruction 找规律打表 C