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;
}
|