CF1490E题解

题解"/>

CF1490E题解

CF1490E题解

• 题目
• • 链接
  • 字面描述
• 思路
• 代码实现

题目

链接

字面描述

描述

现有 n 支队伍参加比赛，每个队伍初始时都有一些积分。

比赛每一轮随机挑两个积分数不为 0 的队伍，然后积分多的队伍获胜，积分少的队伍把积分全部给积分多的队伍（如果积分数量相同则随机挑选一队获胜），直到最后只剩一个队伍， 则这个队伍获胜。

求哪些队伍是有可能获胜的。

输入描述

第一行仅有一个正整数 t ( 1≤t≤10
4
)，表示测试数据的组数。

对于每组测试数据， 第一行仅有一个正整数 n (1≤n≤2⋅10
5
) ，表示队伍数量。

第二行有 n 个正整数 a
1
​
,a
2
​
,…,a
n
​
(1≤a
i
​
≤10
9
)，分别表示队伍的积分。

其中所有测试数据中 n 的总和不超过 2⋅10
5
。

输出描述

依次给出 t 组测试数据的结果，对于每组测试数据，第一行仅有一个数 m，表示可能获胜的人数，第二行包含 m 个数，表示最有可能获胜的队伍的编号。

用例输入 1

2
4
1 2 4 3
5
1 1 1 1 1
用例输出 1

3
2 3 4
5
1 2 3 4 5

思路

若将n人实力先排序
在二分第一个能胜利的人，模拟一遍计算，实力比他大的人一定能胜利

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int maxn=2e5+10;
int t,n,ans,k;
struct node{int x,op;
}a[maxn];
int b[maxn];
inline bool cmp(node u,node v){return u.x<v.x;}
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].x);a[i].op=i;}sort(a+1,a+n+1,cmp);ans=0,k=0;int l=1,r=n;while(l<=r){int mid=(l+r)/2,flag=1;ll cnt=a[mid].x;for(int i=1;i<=n;i++){if(i!=mid){if(cnt<a[i].x){flag=0;break;}cnt+=a[i].x;}}if(flag){ans=mid;r=mid-1;}else l=mid+1;} printf("%d\n",n-ans+1);for(int i=ans;i<=n;i++)b[++k]=a[i].op;sort(b+1,b+k+1);for(int i=1;i<=k;i++)printf("%d ",b[i]);printf("\n");}return 0;
}