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

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

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

C. Array Destruction time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

You found a useless array a">aa of 2n">2n2n positive integers. You have realized that you actually don't need this array, so you decided to throw out all elements of a">aa.

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

  1. In the beginning, you select any positive integer x">xx.
  2. Then you do the following operation n">nn times:
    • select two elements of array with sum equals x">xx;
    • remove them from a">aa and replace x">xx with maximum of that two numbers.

For example, if initially a=[3,5,1,2]">a=[3,5,1,2]a=[3,5,1,2], you can select x=6">x=6x=6. Then you can select the second and the third elements of a">aa with sum 5+1=6">5+1=65+1=6 and throw them out. After this operation, x">xx equals 5">55 and there are two elements in array: 3">33 and 2">22. You can throw them out on the next operation.

Note, that you choose x">xx before the start and can't change it as you want between the operations.

Determine how should you behave to throw out all elements of a">aa.

Input

The first line contains a single integer t">tt (1≤t≤1000">1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains the single integer n">nn (1≤n≤1000">1≤n≤10001≤n≤1000).

The second line of each test case contains 2n">2n2n integers a1,a2,…,a2n">a1,a2,…,a2na1,a2,…,a2n (1≤ai≤106">1≤ai≤1061≤ai≤106) — the initial array a">aa.

It is guaranteed that the total sum of n">nn over all test cases doesn't exceed 1000">10001000.

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 x">xx you've chosen. Print description of n">nn operations next. For each operation, print the pair of integers you remove.

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 a">aa.

a">分析

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

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

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

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

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

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

a">代码

a">https://codeforces.com/contest/1474/submission/105596393

#include 
#include 
#include 
#include 
#include 
#include <string.h>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string.h>
#include 
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",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;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签