P12360 题解

· · 题解

模拟赛 T1。

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

设当前 check 的值是 mid，首先考虑对方的最优排布。对于对方的前 mid 个数已经固定，无需考虑。对于 mid+1\sim n 位，按照 p 从大到小的权值从大到小分布技能值 b_i 对于对方是最优的（即权值更大的比赛场派更强的人去守）。

考虑 b 固定后我方排布 a 的策略。这是一个经典的田忌赛马问题。显然也是按照比赛场的奖金 p 从大到小考虑。有一个贪心的策略是能拿就拿，不妨把能拿下当前场的人叫做「强者」，如果「强者」的策略是不拿下当前场而等到后面的场再去拿下，显然是不优的，因为都能拿下但收益降低了。于是如果当前存在「强者」，一定要直接拿下当前场。

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

如果当前没有「强者」，也就是没有 a 能打过当前的守将，那么就只能输掉这一局。此时排上去当前 a_i 最小也就是最弱的人上去就行了。（反正谁上都是输，留一些较强的说不定后面还有用，最没用的上去顶一下就行了。）

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

每次对战记录上场的我方队员是否能打过守将。如果能打过就加上当前赛场的贡献。check 的返回值即判断总贡献是否能 \ge \lfloor\frac{sum}{2}\rfloor+1，其中 sum=\sum p_i。

复杂度分析：set 带一只 \log，二分带一只 \log。那么复杂度就是 \mathcal{O(n\log^2 n)} 的。

#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;
}