Renting Bikes

Created by LXC on Tue Jul 4 00:02:37 2023

https://codeforces.com/problemset/problem/363/D

ranting: 1800

tag: binary search, greedy

problem

有n个人，m辆车。

现在每个人最多买1辆车，n个人所拥有的钱财是$b_1, b_2, \cdots, b_n$，m辆车的价格是$p_1, p_2, \cdots, p_m$。

n个人有一个公共财产a，代表的是每个人可以在买车时花费总共公费。

现在问n个人最多有多少人能买车，且花费的私人财产之和最小。

solution

假设n个人中有k个能买车，那么首先要有k辆车，然后为了保证能买得起k辆车，我们选择n个人中最富有的k人去买m辆车中最便宜的k辆车。
在这k人k车中，每次选择最富的买最贵的车，如果买不起就公费凑。最后公费是负数则说明n人无法买k辆车，否则可以将剩余的公费分配给这些买车的人，让总体购车私人钱财最小化。

我们知道如果买k辆车能买得起，那么买k-1辆车也能买得起。

所以定义f(x)为买k辆车是否买得起，若是则f(x) = 1，否则f(x) = 0。f(x)为单调非增函数。
我们可以用二分法找到使得f(x)=1的最大x。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, m, a;
    cin >> n >> m >> a;
    vector<ll> b(n), p(m);
    for (auto& i : b)
        cin >> i;
    for (auto& i : p)
        cin >> i;
    sort(b.rbegin(), b.rend());
    sort(p.rbegin(), p.rend());
    int l = 1, r = min(n, m) + 1;
    while (l < r) {
        int c = l + r >> 1;
        // cout << l << " " << r << " " << c << endl;
        ll pub = a, pri = 0;
        for (int i = m - c, j = 0; i < m; i++, j++) {
            pri += min(b[j], p[i]);
            if (b[j] < p[i])
                pub -= p[i] - b[j];
        }
        if (pub < 0) {
            r = c;
        } else {
            l = c + 1;
        }
    }
    int c = l - 1;
    cout << c << " ";
    ll pub = a, pri = 0;
    for (int i = m - c, j = 0; i < m; i++, j++) {
        pri += min(b[j], p[i]);
        if (b[j] < p[i])
            pub -= p[i] - b[j];
    }
    cout << max(pri - pub, 0LL) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}