Codeforces 1月8日dev.2 A题解析

先看题目：

A. Make it Beautiful

time limit per test3 seconds

memory limit per test512 megabytes

inputstandard input

outputstandard output

An array aa is called ugly if it contains at least one element which is equal to the sum of all elements before it. If the array is not ugly, it is beautiful.

For example:

• the array [6,3,9,6][6,3,9,6] is ugly: the element 99 is equal to 6+36+3;

• the array [5,5,7][5,5,7] is ugly: the element 55 (the second one) is equal to 55;

• the array [8,4,10,14][8,4,10,14] is beautiful: 8≠08≠0, 4≠84≠8, 10≠8+410≠8+4, 14≠8+4+1014≠8+4+10, so there is no element which is equal to the sum of all elements before it.

You are given an array aa such that 1≤a1≤a2≤⋯≤an≤1001≤a1≤a2≤⋯≤an≤100. You have to reorder the elements of aa in such a way that the resulting array is beautiful. Note that you are not allowed to insert new elements or erase existing ones, you can only change the order of elements of aa. You are allowed to keep the array aa unchanged, if it is beautiful.

Input

The first line contains one integer tt (1≤t≤20001≤t≤2000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer nn (2≤n≤502≤n≤50). The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤a1≤a2≤⋯≤an≤1001≤a1≤a2≤⋯≤an≤100).

Output

For each test case, print the answer as follows:

• if it is impossible to reorder the elements of aa in such a way that it becomes beautiful, print NO;

• otherwise, in the first line, print YES. In the second line, print nn integers — any beautiful array which can be obtained from aa by reordering its elements. If there are multiple such arrays, print any of them.

Example

input

4

4

3 3 6 6

2

10 10

5

1 2 3 4 5

3

1 4 4

output

YES

3 6 3 6

NO

YES

2 4 1 5 3

YES

1 4 4

题目解释：

题目中给出了一个漂亮数组和丑数组的定义：如果一个数组中，存在某一个元素等于他前面所有项的元素之和，那么他就是丑数组，反之则为漂亮数组。题目中给出了例子。

第一个例子 6 3 9 6 第三个元素9等于前两个元素6，3之和 所以他是丑数组

第二个例子5 5 7 第三个元素5 等于前面元素 5 的和 所以他也是丑数组

第三个例子 不存在某一元素等于前面元素之和 所以是漂亮数组

现在，要求依次输入t（案例次数1<=t<=2000 ），n（表示数组有n个元素 2<=n<=50），紧接着输入n个数代表数组中每个元素，现在你可以对这个数组内的元素进行任意排序，如果经过排序之后可以为漂亮数组 那么输出YES 并且将这个漂亮数组输出，如果无论如何也出现不了漂亮数组，那么输出NO

例如示例1 ：

3 3 6 6 本身是个丑数组 但是经过排序之后可以为 6 3 6 3 变成了一个漂亮数组 那么输出YES 并且把 6 3 6 3输出

思路分析：

这个题目初看起来，判断丑和漂亮上不难理解，但是主要问题在于，如何找到满足条件的漂亮数组，并且到底是yes还是no。这是本题目的两个核心问题。

那么如何解决呢？？？？

思路一：

其实整个数组，判断到底时yes还是no，只要看第一个元素，第二个元素，以及最后一个元素，所以我们只要把数组倒序，特判一下a[0]==a[n-1]和a[0]==a[1]其实就可以了，然后适当的把三个位置的数字换一下顺序就行了。至于详细思路，看思路二更容易理解。

思路一的代码如下

#include<bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<"\n";
#define no cout<<"NO"<<"\n";
const int N = 1e6 + 10;
int b[55];
void solve(){
    int n; cin >> n;
    vector<int>a(n); int fg = 1;
    for (int i = 0; i < n; i++) {
    cin >> a[i];
    }
    if (a[0] == a[n - 1]) { no return; }
    if (n & 1) {
        for (int i = 0; i <(n-1)/2; i++) {
            int t = a[i];
            a[i] = a[n - 1 - i];
            a[n - 1 - i] = t;
        }
    }
    else for (int i = 0; i < n / 2; i++) {
        int t = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = t;
    }
    if (a[1] == a[0]) {
        a[1] = a[n - 1];
        a[n - 1] = a[0];
    }
    yes
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t; cin >> t;
    while (t--) {
        solve();
    }
}

思路二：

我们要注意到一个点，数组中的每个元素都是大于1的，意思就是不会出现0，这是个很重要的地方。我们来看看，根据丑和漂亮的定义，我们既然要漂亮，那么就要保证后面的数字不会等于前面数字相加。

而满足这个条件有两种方法：

1：让前面的和小于这个数

2：让前面的和大于这个数

那么这个时候，我们就要在两个方法里面进行选择。这两个方法都需要我们能确保能满足所对应的条件。

我们看法一，要满足前面的数字的和小于这个数，是不是完全没有控制方法？根本无法确定如何排序能保证和小于这个数，但是法二就不一样了，为什么呢？我们想要和大于这个数，那么是不是只要其中任意一个数大于等于这个数，再加上因为其他数字都大于0， 就可以保证 和 一定大于这个数。所以我们只需要保证前面有数字大于这个数。

那么如何保证呢？很简单，直接把数组进行从大到小排序，那么就可以保证每个数都是第一个到他为止中所有数字中最小的。

按照这个思路，我们应该是可以找到这样的漂亮数组，那么如何去判断是不是会存在呢？其实很简单了，因为我们把数组从大到小排序后：假设为 a1 a2 a3 a4 a5 a6 .....an 那么只有一种情况会出现无法YES 这种情况就是a1到an全部相同。因为只有这样才会出现NO，当数组元素都相同的时候，无论如何排序，其实都一样，就会导致a1=a2，那么有且只有a2的存在就会使得整个数组变成丑函数，因为后面的数字不可能等于前面的数字相加，只能小于；但如果整个数组不是全部相同但是a1=a2时（因为a2是我们唯一的威胁，解决他那么整个问题也就解决了），我们变可以把a1与an进行更换（或者a2与an），这样而来a2的威胁就消失了，这个题目也就迎刃而解了。

思路二代码

#include<stdio.h>
#include <stdlib.h>
int cmp(const void *a,const void *b)
{
    return *(int *)b-*(int *)a;
}
int main()
{
    int t,i,n;
    int g,h,sum,flag;
    int *a;
    scanf("%d",&t);
    for(i=1;i<=t;i++){
        scanf("%d",&n);
        a=(int *)calloc(n,sizeof(int));
        for(g=0;g<n;g++){
            scanf("%d",&a[g]);
        }
        sum=0;
        for(g=0;g<n;g++){
            sum+=a[g];
        }
        if(sum!=a[0]*n){
            printf("YES\n");
            qsort(a,n,sizeof(a[0]),cmp);
            if(a[0]==a[1]){
                t=a[0];
                a[0]=a[n-1];
                a[n-1]=t;
            }
            for(g=0;g<n;g++){
                printf("%d ",a[g]);
            }
            printf("\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
 } 

但是在提交的时候，遇到点问题，思路二的思路绝对没问题，但是在提交之后，测试点二一直过不了，我看了其他的选手的代码，也有不少也是思路二，但是他们的都过了，我和朋友商讨过，暂且没有得出结果。各位大佬如果路过，帮忙看一下是不是代码问题。今天的签到题解析到此为止啦！

老规矩，希望大伙的点赞 收藏 留言 与建议