自动搬运

查看原文

来自洛谷，原作者为

	Bitter_Tea 月光那么美

搬运于2025-08-24 22:42:36，当前版本为作者最后更新于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;
}