codeforce 1474C C. Array Destruction 找规律 打表 C
https://codeforces.com/contest/1474/problem/C
You found a useless array aa of 2n2n positive integers. You have realized that you actually don't need this array, so you decided to throw out all elements of aa.
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 xx.
- Then you do the following operation nn times:
- select two elements of array with sum equals xx;
- remove them from aa and replace xx with maximum of that two numbers.
For example, if initially a=[3,5,1,2]a=[3,5,1,2], you can select x=6x=6. Then you can select the second and the third elements of aa with sum 5+1=65+1=6 and throw them out. After this operation, xx equals 55 and there are two elements in array: 33 and 22. You can throw them out on the next operation.
Note, that you choose 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 aa.
The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.
The first line of each test case contains the single integer nn (1≤n≤10001≤n≤1000).
The second line of each test case contains 2n2n integers a1,a2,…,a2na1,a2,…,a2n (1≤ai≤1061≤ai≤106) — the initial array aa.
It is guaranteed that the total sum of nn over all test cases doesn't exceed 10001000.
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 xx you've chosen. Print description of nn operations next. For each operation, print the pair of integers you remove.
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
YES 6 1 5 2 3 NO NO YES 21 14 7 3 11 5 6 2 4 3 1
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 aa.
分析
题意是要求从整个数组中每次选出来俩数删掉，然后保留最大值，使得下一次删除的两个数之和是这个最大值。
由题意可以画出来一个二叉树。
会发现所有的数中有一个数是无效的，也就是二叉树的顶点的右分支
注意到n是1000，所以肯定要进行一次循环把这个数进行选出来
再注意到排除这个数之后，二叉树的左分支每次只能选择当前数组最大的进行
那么我们可以从后往前进行扫描，每次删除两个数，如果无法删除，则无效，删除的过程可以使用lower_bound加快速度
代码
https://codeforces.com/contest/1474/submission/105596393
#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; }