题解 CF1490E 【Accidental Victory】

珂能并不会有更好的阅读体验

Description

题目 Link

• 有 $n$ 个人，第 $i$ 个人的实力为 $a_i$。
• 要进行 $n-1$ 场比赛，每场比赛淘汰一个人，最后留下的人是赢家。
• 每场比赛都会从现有的人中间随机选取两个人 $p,q$，如果 $a_p>a_q$，则 $p$ 获胜，$q$ 淘汰，并且 $a_p$ 变成 $a_p+a_q$。
• 如果 $a_p=a_q$，那么两人都可以赢，此时输赢随机。
• 若 $a_p<a_q$，与 $a_p>a_q$ 类似。
• 现在，给定 $n$ 个人的实力，求有多少个人可能会赢，他们分别是谁。
• 需要先输出可能会赢的人数，再按照升序输出可能赢的人的编号。
• $t$ 组数据，$1\le t\le 10^4,\sum n\le 2\times10^5,a_i\le10^9$。

先排序，排成升序（排序之前先记录一下每个数的编号）。

然后如果前 $k$ 个加起来都没第 $k+1$ 个大，那前 $k$ 个肯定都没机会赢。

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

毕竟不可能出现 $a_i<a_j$ ，但是 $i$ 可能赢，$j$ 不可能赢这种嘛awa。

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

那记录一个指针，指针后面的数都是能赢的，前面都是不可能赢的。

从前往后扫一遍，同时记录前缀和，如果前缀和小于后面的单独一个数自己，说明前面这一堆都不可能赢了，指针后移。

复杂度 $O(n\log n)$。

哦对，还有一个事：

既然记录了前缀和，那么最多会到：

$10^9\times(2\times10^5)=2\times10^{14}>2^{31}-1$

所以，一定要！！！！开 long long！！！！！！

#include<cstdio>
#include<algorithm>
#include<cctype>

#define int long long

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

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