• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

SEERC 2020 L. Neo-Robin Hood

开发技术 开发技术 6小时前 4次浏览

二分好题,”国内出不出这么有水平的题目”
https://codeforces.com/gym/103102/problem/L

题意

(n) 个人,对于每个人,你可以抢劫他并获得 (m) 的钱,或者给他 (p) 元让他为你担保。抢的人数必须小于等于担保人数,问最多能抢多少人?

Tutorial

先看两个人 (A), (B). 如果抢 (A)(B) 比 抢 (B)(A) 要优,则可以得到 (m_1-p_2geq m_2-p_1),移项有 (m_1+p_1 geq m_2+p_2). 因此可以先按 (val = m+p) 排序
这里其实意味着,交换 (a)(b)两者的代价是 (m_1-p_2 -(m_2-p_1)),设最终偷 (A) 集合,抢 (B) 集合,如果不满足 (max(A) < min(B)),那么此时交换代价为负值,一定交换更优。

排完序后,区间内的顺序还是不完全单调的,可以二分最后抢 (k) 个人,在 check 中枚举区间的分界点 (i), 这表示从 ([1,i]) 中选人抢,([n-i+1,n])中选人买,用两个堆维护区间中的前 (k) 大/小。如果分界点中存在一个是合法的,那么当前 (k) 为true

点击查看代码
#include <bits/stdc++.h>
typedef long long ll;
#define endl 'n'
#define P pair<int, int>
#define eps 1e-8
#define IOS                  
    ios::sync_with_stdio(0); 
    cin.tie(0);              
    cout.tie(0);
using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define int ll
struct node {
    int m, p, val;
} a[N];

int n;
bool cmp(node& lhs, node& rhs) {
    return lhs.val > rhs.val;
}
ll minn[N], maxx[N];
bool check(int k) {
    if (k == 0)
        return 1;
    priority_queue<int, vector<int>, greater<int> > q1;
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        if (i <= k) {
            q1.push(a[i].m);
            res += a[i].m;
        } else {
            if (q1.top() < a[i].m) {
                // mx =
                res -= q1.top() - a[i].m;
                q1.pop();
                q1.push(a[i].m);
            }
        }
        maxx[i] = res;
    }

    res = 0;
    priority_queue<int> q2;
    for (int i = n; i >= 1; i--) {
        if (i >= n - k + 1) {
            q2.push(a[i].p);
            res += a[i].p;
        } else {
            if (q2.top() > a[i].p) {
                // mx =

                res -= q2.top() - a[i].p;
                q2.pop();
                q2.push(a[i].p);
            }
        }
        minn[i] = res;
    }

    for (int i = k; i <= n - k; i++) {
        if (maxx[i] - minn[i + 1] >= 0)
            return true;
    }
    return false;
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].m;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].p;
        a[i].val = a[i].m + a[i].p;
    }
    sort(a + 1, a + n + 1, cmp);

    int l = 1, r = n / 2, mid, ans = 0;

    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
}

程序员灯塔
转载请注明原文链接:SEERC 2020 L. Neo-Robin Hood
喜欢 (0)