第四题，我是真懵

复赛CSP-J/S模拟赛讨论
1

T4这题折腾我1h了，还没好
代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l,r;
struct node{
	int play;
	int score;
	int b=0;
};
node a[100005];
bool cmp1(node x,node y){
	if(x.score!=y.score) return x.score>y.score;
	return x.play<y.play;
}
bool cmp2(node x,node y){
	return x.play<y.play;
}
bool check(int x){
	int t=a[1].score;
	for(int i=2;i<=n;i++) t=(t+a[i].score)/2;
	if(t<=a[x].score) return 1;
	return 0;
}
signed main(){
	freopen("master.in","r",stdin);
	freopen("master.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].score;
		a[i].play=i;
	}
	sort(a+1,a+n+1,cmp1);
	l=1,r=n;
	while(l<r){
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	for(int i=1;i<l;i++) a[i].b=1;
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<=n;i++) cout<<a[i].b;
	return 0;
}

WA,70pts
错误样例:输入：2 1 1
应输出：11
我输出：10

1 个赞
2

你这个二分太离谱了

4

l和r写反了

6

谢谢，变成了0pts

7

@葛牧恒

8

腾讯会议里发的代码改一下就a了

9

屏幕截图 2024-10-13 165253

10

@葛牧恒 我AC了

12

我在努力

13

你自己在腾讯会议里求助的代码

14

@葛牧恒

改成：

bool check(int x){
	long long t=0;
	for(int i=1;i<=n;i++){
        if(i==x)continue;
        else if(t==0)t=a[i].score;
        else t=(t+a[i].score)/2;
    } 
	if(t<=a[x].score) return 1;
	return 0;
}
15

改成:

while(l<r){
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	for(int i=1;i<=l;i++) a[i].b=1;
16

@葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 @葛牧恒 给我解决方案！！！！！！！

17

呜呜呜，我的解决方案～

1 个赞