题解：P12360 [eJOI 2024] 足球决斗 / CF Duels

P12360 [eJOI 2024] 足球决斗 / CF Duels

显然答案具有二分性。

现在我们需要判断当前的

mid

是否可行，即写 check 函数。

考虑我方最劣情况（对方的最优情况），即在后

n - mid

个球场，对方将技能等级按奖金顺序排列（最强的的对应奖金最多的）。

此时我方可以使用类似田忌赛马的思路，优先考虑奖金最大的场地，如果我方等级最高的都干不过，就用最低的干。否则用等级比对方高的人中等级最低的人干。可以用 set 中的 upper_bound 实现。

check 函数

O(n \log n)

，总时间复杂度

O(n \log ^2 n)

。

code

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int T,n;
ll p[N],P[N];
int a[N],b[N],B[N];
set<int>A;
struct node{
	int p,b;
	friend bool operator < (const node &x,const node &y){
		return x.p>y.p;
	}
}C[N];
bool check(int x){
	for(int i=x+1;i<=n;i++)P[i]=p[i],B[i]=b[i];
	sort(P+x+1,P+n+1);
	sort(B+x+1,B+n+1);
	for(int i=1;i<=x;i++)C[i]=node{p[i],b[i]};
	for(int i=x+1;i<=n;i++)C[i]=node{P[i],B[i]};
	sort(C+1,C+n+1);
	for(int i=1;i<=n;i++)A.insert(a[i]);
	ll sum1=0,sum2=0;
	for(int i=1;i<=n;i++){
		auto p=A.upper_bound(C[i].b);//找比对方高的人中最低的
		if(p==A.end()){
			sum2+=C[i].p;
			A.erase(A.begin());
		}
		else{
			sum1+=C[i].p;
			A.erase(p);
		}
	}
	return sum1>sum2;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int l=0,r=n,mid,ans=-1;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

题解：P12360 [eJOI 2024] 足球决斗 / CF Duels

文章操作

相关推荐

评论

题解：P12360 [eJOI 2024] 足球决斗 / CF Duels