P12360 题解

模拟赛 T1。

每次要对没确定的位作最坏的打算，那么当新的一位确定后新的最坏的打算一定不会比之前的更坏，也就是说获得的分数可能会更优。于是答案单调，考虑二分答案。

设当前 check 的值是

mid

，首先考虑对方的最优排布。对于对方的前

mid

个数已经固定，无需考虑。对于

mid+1\sim n

位，按照

p

从大到小的权值从大到小分布技能值

b_i

对于对方是最优的（即权值更大的比赛场派更强的人去守）。

考虑

b

固定后我方排布

a

的策略。这是一个经典的田忌赛马问题。显然也是按照比赛场的奖金

p

从大到小考虑。有一个贪心的策略是能拿就拿，不妨把能拿下当前场的人叫做「强者」，如果「强者」的策略是不拿下当前场而等到后面的场再去拿下，显然是不优的，因为都能拿下但收益降低了。于是如果当前存在「强者」，一定要直接拿下当前场。

而如果有好几个「强者」能打败当前对方守将拿下当前场，显然选技能值最低的「强者」拿下即可。剩余几位技能值较高的留在后面可能会发挥更大的用处。

如果当前没有「强者」，也就是没有

a

能打过当前的守将，那么就只能输掉这一局。此时排上去当前

a_i

最小也就是最弱的人上去就行了。（反正谁上都是输，留一些较强的说不定后面还有用，最没用的上去顶一下就行了。）

显然用 set 可以直接维护我们当前可用人的技能值的集合。

使用 st.lower_bound(x) 寻找最小的能打败守将 $x$ 的「强者」。
如果没有找到「强者」，那就排 st.begin()。
每次从 set 中找到我们当前出战的人员 $y$ 后用 st.erase(y) 将 $y$ 从可用人集合中删除即可。
以上操作都是 $\mathcal{O}(\log n)$ 的，非常快速。

每次对战记录上场的我方队员是否能打过守将。如果能打过就加上当前赛场的贡献。check 的返回值即判断总贡献是否能

\ge \lfloor\frac{sum}{2}\rfloor+1

，其中

sum=\sum p_i

。

复杂度分析：set 带一只

\log

，二分带一只

\log

。那么复杂度就是

\mathcal{O(n\log^2 n)}

的。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n,sum,a[N],b[N];
struct node{int id,val;}w[N];
bool cmp(node X,node Y){return X.val>Y.val;}
bool check(int mid){
	set<int>st1,st2;
	for(int i=1;i<=n;i++){
		st2.insert(b[i]);
		if(i>mid)st1.insert(-a[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int tmp1,tmp2;
		if(w[i].id<=mid)tmp2=a[w[i].id];
		else{
			auto it=st1.begin();
			tmp2=-(*it),st1.erase(it);
		}
		auto tt=st2.lower_bound(tmp2);
		if(tt!=st2.end())tmp1=*tt,st2.erase(tt);
		else tmp1=*st2.begin(),st2.erase(st2.begin());
		if(tmp1>tmp2)ans+=w[i].val;
	}
	return ans>=sum/2+1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i].val,w[i].id=i,sum+=w[i].val;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	sort(w+1,w+n+1,cmp);
	int lt=-1,rt=n+1;
	while(lt+1<rt){
		int mid=lt+rt>>1;
		if(check(mid))rt=mid;
		else lt=mid;
	}
	cout<<(rt==n+1?-1:rt);
	return 0;
}

文章操作

相关推荐

评论

P12360 题解