题解P8800 [蓝桥杯 2022 国 B] 卡牌

Bitter_Tea · 2022-11-11 22:09:59 · 题解

我的做法是二分

有序性是显然的，如果我们不能凑出\ c\ 套牌，那么我们一定不能凑出c+1套牌。

二分的\ l\ 也就是直接由\ a_i\ 凑出的牌的数目，\ r\ 是由\ a_i+b_i\ 凑出的牌的数目。

在判断函数中，如果能当前能凑出期望的\ mid\ 张，那么就把需要手写的加起来，否则直接不符合条件。最后再计较需要的数目\ s\ 和\ m\ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n;
int a[N];
int b[N];
long long m;

bool judge(int x) {
    long long s = 0;
    for (int i = 1; i <= n; i++) {
        if (x - a[i] <= b[i]) {
            s += max(x - a[i], 0);
        }
        else return false;
    }
    if (s <= m) return true;
    return false;
}
int main() {
    cin >> n >> m;
    int l = 0x3f3f3f3f;
    int r = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        l = min(l, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        r = max(r, b[i] + a[i]);
    }
    int ans;
    while (l <= r) {
        int mid = l + r >> 1;
        if (judge(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}