竞技比赛二分0pts求救！！！

杨思越 · 2025 年2 月 7 日 08:33

出于种种原因，这道题没有解决方案

1. 竞技比赛

题目ID：20457必做题文件操作100分

最新提交：

Time Limit Exceeded

0 分

历史最高：

Time Limit Exceeded

0 分

时间限制: 500ms

空间限制: 262144kB

输入文件名: game.in

输出文件名: game.out

题目描述

在一个神秘的竞技场中，有 nn 支队伍参赛，每支队伍初始时拥有一定数量的魔法水晶 aiai。比赛规则如下：
每一轮，竞技场将随机选择两支拥有魔法水晶的队伍进行对决。对决规则为：魔法水晶较多的队伍获胜，并从失败的队伍那里获得所有魔法水晶；如果两支队伍的魔法水晶数量相同，则随机选择获胜者。比赛持续进行，直到场上只剩下一个队伍拥有魔法水晶，成为最终的胜利者。
你的任务是计算，哪些队伍有可能成为最终的胜利者。输出胜利者的人数，然后如果胜利者的人数是大于等于一半的输出 YES，否则的话就输出 NO 。

输入格式

第一行输入一个整数 nn。
第二行输入 nn个整数 aiai,表示每个人所拥有的魔法水晶的数量。

输出格式

第一行输出胜利者人数。
第二行输出一行 YES 或者 NO。

样例

Input 1

10 5 4 10 9 1918 888 1 2 3 666

Output 1

1 NO

数据范围

对于 3030% 的
1<=n<=1031<=n<=103
1<=ai<=1061<=ai<=106
对于 100100% 的数据
1<=n<=1051<=n<=105
1<=ai<=1091<=ai<=109

二分了，但是TLE代码:

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;//赢得次数 
long long a[100005];
long long sum[100005];
bool cmp(long long x,long long y){
	return x<y;
}
bool win(int ii){//判断编号为ii的队伍是否能获胜 
	long long now=sum[ii];
	for(int j=ii+1;j<=n;j++){
		if(now>a[j]){
			now+=a[j];
			continue;
		}
		if(now==a[j]){
			continue;
		}
		return 0;
	}
	return 1;
}
void fen_2(){
	int l=1;
	int r=n;
	while(l<r){
		int mid=(l+r)/2;//假设有mid个队伍能获胜，则意味着获胜范围为n-mid+1,n
		if(a[n-mid+1]==a[n-mid]){//假设不成立 
			r=mid;
			continue;
		}
		if(win(n-mid+1)){//如果这个范围中魔法值最低的队伍也能获胜 
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	if(l*2>=n){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}

int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	if(n==1){
                cout<<1<<endl;
		cout<<"YES";
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		cout<<win(i)<<endl;
	}
	fen_2();
	return 0;
}
/*

*/

桑沫严 · 2025 年2 月 7 日 08:38

@杨思越发现一个问题： n=1 时没有输出 1 ，只输出了 YES

桑沫严 · 2025 年2 月 7 日 08:39

你这个调试是不是没删

桑沫严 · 2025 年2 月 7 日 08:41

而且你这个写得不对，因为如果相等是随机选择，也可能获胜，所以应该是：

        if(now>=a[j]){
			now+=a[j];
			continue;
		}

杨思越 · 2025 年2 月 7 日 08:41

WA10pts
你真是个甜菜

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;//赢得次数 
long long a[100005];
long long sum[100005];
bool cmp(long long x,long long y){
	return x<y;
}
bool win(int ii){//判断编号为ii的队伍是否能获胜 
	long long now=sum[ii];
	for(int j=ii+1;j<=n;j++){
		if(now>a[j]){
			now+=a[j];
			continue;
		}
		if(now==a[j]){
			continue;
		}
		return 0;
	}
	return 1;
}
void fen_2(){
	int l=1;
	int r=n;
	while(l<r){
		int mid=(l+r)/2;//假设有mid个队伍能获胜，则意味着获胜范围为n-mid+1,n
		if(a[n-mid+1]==a[n-mid]){//假设不成立 
			r=mid;
			continue;
		}
		if(win(n-mid+1)){//如果这个范围中魔法值最低的队伍也能获胜 
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	if(l*2>=n){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}

int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	if(n==1){
		cout<<1<<endl;
		cout<<"YES";
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	/*
	for(int i=1;i<=n;i++){
		cout<<win(i)<<endl;
	}
	*/
	fen_2();
	return 0;
}
/*

*/

桑沫严 · 2025 年2 月 7 日 08:42

你看见我上面发的没

桑沫严 · 2025 年2 月 7 日 08:43

所以这个你也得删掉

桑沫严 · 2025 年2 月 7 日 08:43

A了吗

杨思越 · 2025 年2 月 7 日 08:43

还是WA10pts

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;//赢得次数 
long long a[100005];
long long sum[100005];
bool cmp(long long x,long long y){
	return x<y;
}
bool win(int ii){//判断编号为ii的队伍是否能获胜 
	long long now=sum[ii];
	for(int j=ii+1;j<=n;j++){
		if(now>=a[j]){
			now+=a[j];
			continue;
		}
		return 0;
	}
	return 1;
}
void fen_2(){
	int l=1;
	int r=n;
	while(l<r){
		int mid=(l+r)/2;//假设有mid个队伍能获胜，则意味着获胜范围为n-mid+1,n
		if(a[n-mid+1]==a[n-mid]){//假设不成立 
			r=mid;
			continue;
		}
		if(win(n-mid+1)){//如果这个范围中魔法值最低的队伍也能获胜 
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	if(l*2>=n){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}

int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	if(n==1){
		cout<<1<<endl;
		cout<<"YES";
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	/*
	for(int i=1;i<=n;i++){
		cout<<win(i)<<endl;
	}
	*/
	fen_2();
	return 0;
}
/*

*/

桑沫严 · 2025 年2 月 7 日 08:44

吴梓峤 · 2025 年2 月 7 日 08:44

咋写那么长？

桑沫严 · 2025 年2 月 7 日 08:45

因为他把二分单独写了个函数

杨思越 · 2025 年2 月 7 日 08:45

WA0pts

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;//赢得次数 
long long a[100005];
long long sum[100005];
bool cmp(long long x,long long y){
	return x<y;
}
bool win(int ii){//判断编号为ii的队伍是否能获胜 
	long long now=sum[ii];
	for(int j=ii+1;j<=n;j++){
		if(now>=a[j]){
			now+=a[j];
			continue;
		}
		return 0;
	}
	return 1;
}
void fen_2(){
	int l=1;
	int r=n;
	while(l<r){
		int mid=(l+r)/2;//假设有mid个队伍能获胜，则意味着获胜范围为n-mid+1,n
		if(win(n-mid+1)){//如果这个范围中魔法值最低的队伍也能获胜 
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
	if(l*2>=n){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}

int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	if(n==1){
		cout<<1<<endl;
		cout<<"YES";
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	/*
	for(int i=1;i<=n;i++){
		cout<<win(i)<<endl;
	}
	*/
	fen_2();
	return 0;
}
/*

*/

桑沫严 · 2025 年2 月 7 日 08:45

请格式化

2345安全卫士 · 2025 年2 月 7 日 08:47

我来抢解决了

张乐凡 · 2025 年2 月 7 日 08:48

不要直接输出 l ，输出 n-l+1

桑沫严 · 2025 年2 月 7 日 08:48

这个写错了，因为你二分的是能获胜的队伍数量，所以应该是：

        if(win(n-mid+1)){//如果这个范围中魔法值最低的队伍也能获胜 
			l=mid;
		}
		else{
			r=mid-1;
		}

然后前面的应该是：

int mid=(l+r+1)/2;

杨思越 · 2025 年2 月 7 日 08:48

还是0

#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;//赢得次数 
long long a[100005];
long long sum[100005];
bool cmp(long long x,long long y){
	return x<y;
}
bool win(int ii){//判断编号为ii的队伍是否能获胜 
	long long now=sum[ii];
	for(int j=ii+1;j<=n;j++){
		if(now>=a[j]){
			now+=a[j];
			continue;
		}
		return 0;
	}
	return 1;
}
void fen_2(){
	int l=1;
	int r=n;
	while(l<r){
		int mid=(l+r)/2;//假设有mid个队伍能获胜，则意味着获胜范围为n-mid+1,n
		if(win(n-mid+1)){//如果这个范围中魔法值最低的队伍也能获胜 
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<n-l+1<<endl;
	if(l*2>=n){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}

int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	if(n==1){
		cout<<1<<endl;
		cout<<"YES";
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	/*
	for(int i=1;i<=n;i++){
		cout<<win(i)<<endl;
	}
	*/
	fen_2();
	return 0;
}
/*

*/

桑沫严 · 2025 年2 月 7 日 08:49

他二分的是能获胜的队伍数量

桑沫严 · 2025 年2 月 7 日 08:49

@杨思越还是写 l，按我的来