球球大作战

NC248199. 球球大作战

描述

注：在本题中，我们会做一些与游戏本身不完全相同的设定，玩过游戏与否对理解题目没有影响。

小橙汁和朋友们正在玩《球球大作战》，在这个游戏中有 $n$ 个玩家，每个玩家将操作一个球，且初始时第 $i$ 个玩家的球的大小为 $a_i$ 。

$n$ 个玩家之间将进行 $n-1$ 次碰撞，每次碰撞发生在两个未淘汰的玩家之间：

1. 玩家 A 的球大小为 $a_1$ ，玩家 B 的球大小为 $a_2$ 。
2. 若玩家 A 的球的大小大于玩家 B 的球的大小，则玩家 B 被淘汰， 且玩家 A 的球的大小变为 $\lfloor \frac{a_1+a_2}{2} \rfloor$ 。反之亦然。
3. 若两名玩家的球的大小相同，游戏系统将随机判定其中一名玩家被淘汰，另一名玩家的球的大小保持不变。

这样，最终仅剩余一名玩家未淘汰，成为胜利者。

对于每个玩家 $1 \le i \le n$ ，询问是否存在一种碰撞顺序，使得该名玩家可以成为最终的胜利者。

输入描述

第一行输入一个正整数 ，表示玩家的数量。

第二行输入  个正整数，第  个正整数  表示初始化时第  个玩家的球的大小。

输出描述

输出一个长度为  的仅有 '0' 和 '1' 组成的字符串，字符串的第  位为 1 当且仅当存在一种碰撞顺序，使得第  名玩家可以成为最终的胜利者。

示例1

输入:

3
5 7 6

输出:

说明:

如下安排碰撞顺序，玩家 $2$ 可取胜：
第一轮，玩家 $2$ 与玩家 $3$ 碰撞，玩家 $2$ 更大而胜出，大小变为 $\lfloor\frac{7+6}{2}\rfloor=6$ ；
第二轮，玩家 $2$ 与玩家 $1$ 碰撞，玩家 $2$ 更大而胜出，大小变为 $\lfloor\frac{6+5}{2}\rfloor=5$ 。

如下安排碰撞顺序，玩家 $3$ 可取胜：
第一轮，玩家 $1$ 与玩家 $2$ 碰撞，玩家 $2$ 更大胜出，大小变为 $\lfloor\frac{7+5}{2}\rfloor=6$ ；
第二轮，玩家 $2$ 与玩家 $3$ 碰撞，玩家 $2$ 和玩家 $3$ 等大小，玩家 $3$ 有机会胜出，大小保持不变。

无论如何安排碰撞顺序，玩家 $1$ 都无法胜出。

示例2

输入:

10
729 9 81 19683 1 2187 3 27 243 6561

输出:

1001010011

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 489ms, 内存消耗: 40872K, 提交时间: 2023-02-11 13:11:23

n=int(input())
A=list(map(int,input().split()))
ret=[0]*n
# print(ret)
num=[]
for index,value in enumerate(A):
    num.append((value,index))
num.sort(key=lambda x:x[0],reverse=True)
l=0
r=n-1
def check(x):
    ret=num[0][0]
    for i in range(n):
        if i==x:
            continue
        ret=(ret+num[i][0])//2
    if num[x][0]>=ret:
        return True
    return False
while l<r:
    mid=(l+r+1)//2
    if check(mid):
        l=mid
    else:
        r=mid-1
for i in range(l+1):
    ret[num[i][1]]=1
for i in ret:
    print(i,end="")

C++(g++ 7.5.0) 解法, 执行用时: 35ms, 内存消耗: 1324K, 提交时间: 2023-02-11 01:23:42

#include<bits/stdc++.h>

using namespace std;
using i64=long long;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	int n;
	cin>>n;

	vector<int>a(n);
	for(int i=0;i<n;i++)
		cin>>a[i];
	auto b=a;

	sort(a.begin(),a.end());

	int l=0,r=n-1;
	while(l<r)
	{
		int m=l+r>>1;
		int s=a[n-1];
		for(int i=n-1;i>=0;i--)
			if(i!=m)
				s=(s+a[i])/2;

		if(s<=a[m]) r=m;
		else l=m+1;
	}

	for(int i=0;i<n;i++)
	{
		if(b[i]>=a[r])
			cout<<1;
		else 
			cout<<0;
	}

	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 73ms, 内存消耗: 2084K, 提交时间: 2023-05-02 18:55:53

#include<bits/stdc++.h>
using namespace std;
long long  a[100010],b[100010];
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(a+1,a+n+1);
	int l=1,r=n;
	while(r>l)
	{
		int mid=(r+l)/2;
		int ant=a[n];
		for(int i=n;i>=1;i--)
			if(i!=mid)
				ant=(ant+a[i])/2;
		if(a[mid]>=ant) r=mid;
		else l=mid+1;
	}
	for(int i=1;i<=n;i++)
		if(b[i]>=a[l]) cout<<1;
		else cout<<0;
	
	
	return 0;
}