题解"/>
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;
}
更多推荐
CF1490E题解
发布评论