CF1646B

崔化博 · 2022-03-11 07:41:08 · 题解

题目的意思其实就是对于每一个数列，每一个数可以是蓝的也可以是红的，也可以不选，然后规定红的数量必须小于蓝的数量，且把红的所有数字和加起来要大于蓝的数字加起来。然后问有没有这种方案。

思路

贪心。我们先试试蓝的选 2 个最小的，红的选 1 个最大的。然后依次加，变成 3 4 5 6 ....个最小的，以及红的 2 3 4 5 .....个最大的，然后看和能否超过就好了。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define int long long 
using namespace std;
int t,n,a[2*1000000+2];
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(register int i=1;i<=n;++i){
            cin>>a[i];
        }
        unsigned long long sum1=0,sum2;
        sort(a+1,a+n+1);
        sum2=a[1];
        for(int i=2,j=n;i<=n/2+1;++i,--j){
            sum2+=a[i];
            sum1+=a[j];
            if(sum1>sum2)
                break;
        }
        if(sum1>sum2)
            cout<<"YES";
        else
            cout<<"NO";
        cout<<endl;
    }
    return 0;
}