题解：P10747 [SEERC2020] Neo-Robin Hood

oMin0 · 2024-07-11 09:23:05 · 题解

建议降蓝。

分析

首先警示后人，题目并不要求你按照 1\sim n 的顺序依次操作，你可以按任意顺序做选择，感觉它没说明白。

考虑这样一件事情，假如我们盗窃了 i，然后用 j 取消仇恨，那么最优策略必然满足 m_i-p_j\geq m_j-p_i，否则可以交换对这两人执行的操作。

这意味着按照 m_i+p_i 排序后，被盗窃的人家和被贿赂的人家存在一个分界点。我们枚举分界点，那然后一定是对前缀 m_i 的前 k 大盗窃，并给后缀 p_i 的前 k 小送钱。用二分+主席树即可做到 O(n\log^2 n)，不过更好写的办法是先二分答案 ans，然后用堆维护固定 k 的前 k 小信息，具体实现见代码。

代码

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
#define int long long
#define endl "\n"

int n,m[100005],p[100005],bh[100005];
bool cmp(int x,int y) {return m[x]+p[x]>m[y]+p[y];}

int sumq[100005],sumh[100005];
bool ck(int k)
{
    priority_queue <int,vector<int>,greater<int>> Q;
    int ns=0;
    for(int i=1;i<=n;i++)
    {
        if(Q.size()<k) Q.push(m[bh[i]]),ns+=m[bh[i]];
        else 
        {
            int nr=Q.top(); ns-=nr; Q.pop(); ns+=max(nr,m[bh[i]]); Q.push(max(nr,m[bh[i]]));
        }
        sumq[i]=ns;
    //  cout<<i<<" "<<sumq[i]<<endl;
    }
    ns=0; while(!Q.empty()) Q.pop();
    for(int i=n;i>=1;i--)
    {
        if(Q.size()<k) Q.push(p[bh[i]]),ns+=p[bh[i]];
        else 
        {
            int nr=Q.top(); ns-=nr; Q.pop(); ns+=max(nr,p[bh[i]]); Q.push(max(nr,p[bh[i]]));
        }
        sumh[i]=-ns;
        //cout<<i<<" "<<sumh[i]<<endl;
    }
    for(int i=k;i+k<=n;i++) if(sumq[i]>=sumh[i+1]) return 1; return 0;
}

signed main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>m[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) bh[i]=i; sort(bh+1,bh+n+1,cmp);
    for(int i=1;i<=n;i++) p[i]=-p[i];
    int l=1,r=n/2;
    while(l<=r) {int mid=(l+r)>>1; if(ck(mid)) l=mid+1; else r=mid-1;} 
    cout<<r<<endl;
}