关于今天 CF 的 E
  • 板块学术版
  • 楼主云浅知处はなび
  • 当前回复13
  • 已保存回复13
  • 发布时间2021/2/17 00:40
  • 上次更新2023/11/5 03:10:59
查看原帖
关于今天 CF 的 E
307453
云浅知处はなび楼主2021/2/17 00:40

先排序,排成升序

然后

如果前 kk 个加起来都没第 k+1k+1 个大

那前 kk 个肯定都没机会赢

并且注意到这个东西一定是最大的一些数能赢

毕竟不可能出现 ai<aja_i<a_j,但是 ii 可能赢,jj 不可能赢这种

就像您比云浅强,不考虑其他因素,那么不可能云浅能1=但是您无论如何都1=不了

那记录一个指针,从前往后扫

同时记录前缀和,如果前缀和小于后面的单独一个数自己,指针后移

复杂度 O(nlogn)O(n\log n)

并且我考虑到了这个:

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;
}
2021/2/17 00:40
加载中...