题解：P10747 [SEERC 2020] Neo-Robin Hood

· · 题解

这题在 XCPC 模拟赛中出了，然后赛时思路全对，结果代码炸了调不出来，急眼了。

首先看到这是一个需要你制定顺序的题目，考虑微扰贪心，对于只有两个人的情况，我应该偷谁还谁，解除仇恨在本文中称为还钱。

对于两个人，其偷钱和还钱的钱分别为 p_1,m_1,p_2,m_2，如果我先偷 1 比先偷 2 更优，那么一定要满足 p_1-m_2 \ge p_2-m_1 移项得 p_1+m_1\ge p_2+m_2，这就是我们的排序方法。

然后考虑如何计算答案，注意到答案显然是有单调性的，所以我们考虑二分答案，我们排完序之后，偷前面的比偷后面的优，所以我们考虑枚举一个断点，使得断点前面的选出 k 个得钱最多的来偷，断点后面的选出 k 个还钱最少的还，这可以使用 priority_queue 来维护，最后判断就做完了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
constexpr int N=1e5+10;
int n,pre[N],suf[N];
struct node{int m,p;}a[N];
inline int reads(){
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    return x*f;
}bool check(int k){
    priority_queue<int> q2;
    priority_queue<int,vector<int>,greater<int> >q1;
    memset(pre,0,sizeof(pre));
    memset(suf,0x3f,sizeof(suf));
    int cnt=0;
    for(int i=1;i<=n;i++){
        q1.push(a[i].m),cnt+=a[i].m;
        if(q1.size()>k) cnt-=q1.top(),q1.pop();
        pre[i]=cnt;
    }cnt=0;for(int i=n;i>=1;i--){
        q2.push(a[i].p),cnt+=a[i].p;
        if(q2.size()>k) cnt-=q2.top(),q2.pop();
        suf[i]=cnt;
    }
//  cout<<"-----------------------\n";
//  cout<<k<<"\n";
//  for(int i=1;i<=n;i++) cout<<pre[i]<<" ";
//  puts("");
//  for(int i=1;i<=n;i++) cout<<suf[i]<<" ";
//  puts("");
    for(int i=k;i+k<=n;i++){
        if(pre[i]>=suf[i+1]) return 1;
    }return 0;
}
signed main(){
    n=reads();
    for(int i=1;i<=n;i++) a[i].m=reads();
    for(int i=1;i<=n;i++) a[i].p=reads();
    sort(a+1,a+n+1,[](node a,node b){return a.m+a.p>b.m+b.p;});
    int L=0,R=n/2,ans=0;
    while(L<=R){
        int mid=(L+R)>>1;
        if(check(mid)) ans=mid,L=mid+1;
        else R=mid-1;
    }printf("%lld\n",ans);
    return 0;
}
/*
5
2 3 4 5 6
1 2 3 4 5
*/