题目链接

题目大意：

题意：你是劫富济自己的罗宾汉，有n个富人，第i个人有m[i]元财富，收买他需要p[i]元。对每个人你都可以选择1.抢他，你获得m[i]元，2.不对他进行操作，3.花p[i]元收买他，他为你开脱你的一件抢劫罪行。你有一个奇怪的目标：抢的人数越多越好，但是你的每一个罪行都必须被开脱。

翻译一下就是抢k个人，收买另外k个人，抢来的钱要足够收买的花费，最大化的k。

解题思路：

1. 首先我们发现如果 j < k j<k j<k并且 k k k是合法的话那么 j j j肯定是可以的那么这样子就答案就是存在存在二分的？

2. 我们先看看假设现在我们已经选择了 2 ∗ k 2*k 2∗k个人了，现在我们只能通过交换两个集合里面元素 e g : 偷 j 买 i → 偷 i 买 j eg:偷j买i\rightarrow 偷i买j eg:偷j买i→偷i买j

3. 我们知道 S S S集合为偷的集合， T T T的集合为买的集合，那么 S = ∑ m i , P = ∑ p j S=\sum m_i,P=\sum p_j S=∑mi​,P=∑pj​

4. 那么合法的集合就是 S − T ≥ 0 S-T\ge0 S−T≥0

5. 我们就是通过不段交调整换去使得 S − T ≥ 0 S-T\ge0 S−T≥0

6. 交换 i 和 j i和j i和j → \rightarrow → ( S − m i + m j ) − ( T − p j + p i ) ≥ 0 (S-m_i+m_j)-(T-p_j+p_i)\ge0 (S−mi​+mj​)−(T−pj​+pi​)≥0

7. 化简得 S − T + ( m j + p j ) − ( m i + p i ) ≥ 0 S-T+(m_j+p_j)-(m_i+p_i)\ge0 S−T+(mj​+pj​)−(mi​+pi​)≥0

8. 根据上面得式子我们肯定是贪心偷 m i + p i m_i+p_i mi​+pi​大的人最好！！

9. 现在我们可以按照 m i + p i m_i+p_i mi​+pi​排序，但是怎么选出 k k k个人呢？
   就是我们知道按照大到小排好续之后偷肯定是前面的，买后面的，那么哲两部分肯定是有一个 边界线的，那么我们可以去枚举，边界线去判断。

10. 我们从 [ 1 , x ] [1,x] [1,x]里面偷从 [ x + 1 , n ] [x+1,n] [x+1,n]里面买嘛，判断一下就可以了

AC code

#include <bits/stdc++.h>
#define mid ((l + r + 1) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 500010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
   read(first);
   read(args...);
}
struct node {
   int mi, pi;
   bool operator < (const node & a){
       if(mi + pi == a.mi + a.pi) return mi > a.mi;
       else return mi + pi > a.mi + a.pi;
   }
}e[maxn];
int n;
ll frontmax[maxn], bemin[maxn];
bool check(int pe) {
    if(!pe) return 1;
    ms(frontmax,0); // 偷大的
    ms(bemin,LLF); // 买便宜的
    multiset<int> premax;
    priority_queue<int> aftmin;
    ll sum = 0;
    for(int i = 1; i <= n; ++ i) {
        if(premax.size() < pe) {// 动态维护前pe大
            sum += e[i].mi;
            premax.insert(e[i].mi);
            frontmax[i] = sum;
            continue;
        } 
        if(*premax.begin() < e[i].mi) {
            frontmax[i] = frontmax[i-1] + e[i].mi - (*premax.begin());
            premax.erase(premax.begin());
            premax.insert(e[i].mi);
        }
        else frontmax[i] = frontmax[i-1];
    }

    sum = 0;
    for(int i = n; i >= 1; -- i) {
        if(aftmin.size() < pe) {
            sum += e[i].pi;
            aftmin.push(e[i].pi);
            bemin[i] = sum;
            continue;
        }
        if(aftmin.top() > e[i].pi) {
            bemin[i] = bemin[i+1] + e[i].pi - aftmin.top();
            aftmin.pop();
            aftmin.push(e[i].pi);
        } else bemin[i] = bemin[i+1];
    }

    for(int i = pe; i <= n - pe; ++ i) 
      if(frontmax[i] >= bemin[i+1])
        return 1;
    return 0;
}

int main() {
    IOS;
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> e[i].mi;      
    for(int i = 1; i <= n; ++ i) cin >> e[i].pi;
    sort(e+1,e+1+n);
    int l = 0, r = n / 2;
    while(l < r) {
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l;
    return 0;
}