Codeforces Round #572 (Div. 2)B

小灰灰 2023-08-17 15:40 156阅读 0赞

# B. Number Circle #

题目链接：[http://codeforces.com/contest/1189/problem/B][http_codeforces.com_contest_1189_problem_B]

题目：

You are given n numbers a1,a2,…,an. Is it possible to arrange them in a circle in such a way that every number isstrictlyless than the sum of its neighbors?For example, for the array\[1,4,5,6,7,8\], the arrangement on the left is valid, while arrangement on the right is not, as5≥4+1and8>1+6

![1705372-20190706114819813-544453932.png][]

InputThe first line contains a single integern(3≤n≤105) — the number of numbers.The second line containsnintegersa1,a2,…,an(1≤ai≤109) — the numbers. The given numbers are not necessarily distinct (i.e. duplicates are allowed).  
OutputIf there is no solution, output "NO" in the first line.If there is a solution, output "YES" in the first line. In the second line outputn  
numbers — elements of the array in the order they will stay in the circle. The first and the last element you output are considered neighbors in the circle. If there are multiple solutions, output any of them. You can print the circle starting with any element.  
Examples  
Input  
32 4 3  
Output  
YES

4 2 3  
Input  
51 2 3 4 4  
Output  
YES

4 4 2 1 3  
Input  
313 8 5  
Output  
NO  
Input  
41 10 100 1000  
Output  
NO  
Note

One of the possible arrangements is shown in the first example:4<2+3;2<4+3;3<4+2.One of the possible arrangements is shown in the second example.No matter how we arrange13,8,5in a circle in the third example,13will have8and5as neighbors, but13≥8+5.There is no solution in the fourth example.

题意：给出一些数，判断这些数能否组成一个环，使得每个数严格小于相邻两个数之和，若可以，按顺序打印环中数字

思路：

先给这些数排序，建立两个数组是sh,ch，再找出最大值，最大值存入一个数组中sh，一个数组从排序后的数从后往前，每隔一个数存入该数组sh，另一个数存入另一个数组ch，再建立一个数组b,sh数组从前往后存入b，ch数组从后往前存入b，这样b中存的就是一个优化的环，只要暴力判断b中每个数是否小于相邻两个数之和即可，若不可以输出NO，可以把b数组输出.

![1705372-20190706115050676-299643876.png][]

#include<bits/stdc++.h>
        typedef long long ll;
        using namespace std;
        const int maxn=1e5+7;
        int main()
        {
         
            int n;
            while(cin>>n) {
                ll a[maxn];
                vector<int>sh,ch;
                for (int i = 0; i < n; i++) {
                    cin >> a[i];
                }
                sort(a, a + n);
                sh.push_back(a[n-1]);
               for(int i=n-2;i>=0;i--)
               {
                  if(i%2==1)
                      ch.push_back(a[i]);
                  else
                      sh.push_back(a[i]);
               }
        //       cout<<"sh="<<endl;
        //       for(int i=0;i<sh.size();i++)
        //           cout<<sh[i]<<" ";
        //       cout<<endl;
        //       cout<<"ch="<<endl;
        //        for(int i=0;i<ch.size();i++)
        //            cout<<ch[i]<<" ";
        //        cout<<endl;
               int b[maxn];
               int book=0;
               for(int i=0;i<sh.size();i++)
               {
                   b[book++]=sh[i];
               }
               for(int i=ch.size()-1;i>=0;i--)
               {
                   b[book++]=ch[i];
               }
        //        cout<<"b="<<endl;
        //        for(int i=0;i<n;i++)
        //            cout<<b[i]<<" ";
        //        cout<<endl;
                bool flag=true;
                for(int i=1;i<n-1;i++)
                {
                    if(b[i]>=b[i-1]+b[i+1])
                    {
                        flag= false;
                        break;
                    }
                }
                if(!flag)
                    cout<<"NO"<<endl;
                else
                {
                    if(b[0]<b[1]+b[n-1])
                    {
                        cout<<"YES"<<endl;
                        for(int i=0;i<n;i++)
                            cout<<b[i]<<" ";
                        cout<<endl;
                    }
                    else
                        cout<<"NO"<<endl;
                }
            }
            return 0;
        }

转载于:https://www.cnblogs.com/Vampire6/p/11142302.html

[http_codeforces.com_contest_1189_problem_B]: http://codeforces.com/contest/1189/problem/B
[1705372-20190706114819813-544453932.png]: /images/20230810/153d571c4c904b7692428d27cee57e08.png
[1705372-20190706115050676-299643876.png]: /images/20230810/484e2e20e9ef4e6eaa6843b58efafde3.png