先排序,排成升序
然后
如果前 k 个加起来都没第 k+1 个大
那前 k 个肯定都没机会赢
并且注意到这个东西一定是最大的一些数能赢
毕竟不可能出现 ai<aj,但是 i 可能赢,j 不可能赢这种
就像您比云浅强,不考虑其他因素,那么不可能云浅能1=但是您无论如何都1=不了
那记录一个指针,从前往后扫
同时记录前缀和,如果前缀和小于后面的单独一个数自己,指针后移
复杂度 O(nlogn)
并且我考虑到了这个:
On the next line print the numbers of these players in increasing order
确实是 increasing order 输出的
所以
有啥问题
#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
struct Node{
int val,id;
};
bool cmp(Node p,Node q){
return (p.val==q.val)?(p.id<q.id):p.val<q.val;
}
int t,n;
Node a[200005];
int b[200005];
int main(void){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].val);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
int sum=0;
int k=1;
for(int i=1;i<n;i++){
sum+=a[i].val;
if(sum<a[i+1].val)k=i+1;
}
printf("%d\n",n-k+1);
int cnt=0;
for(int i=k;i<=n;i++){
b[++cnt]=a[i].id;
}
sort(b+1,b+cnt+1);
for(int i=1;i<=cnt;i++)printf("%d ",b[i]);
puts("");
}
return 0;
}