Lotuses's Blog

CF1646B Solution

  • 742 字
  1. 1. Solution

Solution

贪心。想要 和大于 和，而且 数量还得更少，那么只能让 中的元素远远大于 中元素。

那么排一遍升序，从左到右选，左边选 个数当做 ，右边选择 个数当做 ，如果扫完全序列都不能满足，那必然是 nO 了。

单次 ，均摊总时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
long long a[1000001];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        long long s1=a[1]+a[2],s2=a[n];
        int i=2,j=n;
        bool flag=0;
        while(i+1<j)
        {
            if(s1<s2) {flag=1;break;}
            i++;j--;
            s1+=a[i];s2+=a[j];
        }
        if(s1<s2) flag=1;
        if(flag) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可