2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020) L Neo-Robin Hood

题目描述

https://codeforces.com/gym/103102/problem/L

简要题意：给定 $n$ 个数对 $(m_i,p_i)$，现在要求选择尽量多的数对，不妨设选择了 $2\times k$ 个，则需保证恰好有 $k$ 个数对取第一位 $m_i$，同时恰好有 $k$ 个数对取第二维 $p_i$，且需保证 $\sum m\ge \sum p$，求最多取多少个数对

$n\le 10^5$

Solution

我们不妨假设一定取 $(m_1,p_1)$ 和 $(m_2,p_2)$ 这两个数对，那么谁应该取第一维，谁应该取第二维，我们简单列一个不等式容易得到当 $m_1+p_1\ge m_2+p_2$ 时我们一定取 $m_1$ 和 $p_2$

那么我们考虑先将所有点排个序，那么我们最终的选择中，取 $m$ 的一定都在取 $p$ 的前面，我们考虑二分答案 $x$，然后我们枚举一个分界点 $i$，对于 $[1,i]$ 我们取 $k$ 个 $m$，对于 $[i+1,n]$ 我们取 $k$ 个 $p$，这里我们用两个堆维护前 $k$ 小和前 $k$ 大即可

时间复杂度 $O(n\log^2 n)$

#include <iostream>
#include <algorithm>
#include <queue>
#define maxn 100010
#define ll long long
using namespace std;

int n;

struct node {
    int x, y;

    friend bool operator < (const node &u, const node &v) {
        if (u.x + u.y == v.x + v.y) return u.x > v.x;
        return u.x + u.y > v.x + v.y;
    } 
} a[maxn];

ll pre[maxn], suf[maxn];
bool check(int x) {
    priority_queue<int, vector<int>, greater<int>> q;
    priority_queue<int> Q; pre[x] = suf[n - x + 1] = 0; 
    for (int i = 1; i <= x; ++i) q.push(a[i].x), pre[x] += a[i].x;
    for (int i = x + 1; i <= n; ++i) 
        if (a[i].x > q.top()) {
            pre[i] = pre[i - 1] - q.top() + a[i].x;
            q.pop(); q.push(a[i].x);
        } else pre[i] = pre[i - 1];
    for (int i = n - x + 1; i <= n; ++i) Q.push(a[i].y), suf[n - x + 1] += a[i].y;
    for (int i = n - x; i; --i) 
        if (a[i].y < Q.top()) {
            suf[i] = suf[i + 1] - Q.top() + a[i].y;
            Q.pop(); Q.push(a[i].y);
        }
        else suf[i] = suf[i + 1];
    for (int i = x; i <= n - x; ++i)
        if (pre[i] >= suf[i + 1]) return 1;
    return 0;
}
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    sort(a + 1, a + n + 1); 
    int l = 1, r = n / 2, mid, ans = 0;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1; 
    } cout << ans << "\n";
    return 0;
}