ABC374E 题解

好题。爱做。

标签：二分。

求最大的最小值，考虑二分答案。然后问题就转化成了（求 \(n\) 次）：有两种物品，每种物品有一个代价和价值，求获得不少于给定价值所需的最小代价。

下文记物品的代价为 \(w\)，价值为 \(v\)，所拿的数量为 \(cnt\)。

假设有两种物品 \(S\) 与 \(T\)，\(S\) 物品的性价比（价值 / 代价）比 \(T\) 高，那么有一种较优的拿法是全拿 \(S\)。但手玩一下发现，这不一定是最优的。那我们从大到小枚举所拿 \(S\) 物品的个数，剩下的价值用 \(T\) 物品补齐，然后计算出代价，取最小值即可。

但是直接枚举是会 TLE 的。注意到当我们拿了很多的 \(T\) 物品的时候，我们把若干 \(T\) 物品替换成相同价值的 \(S\) 物品会更优。具体地说，假如 \(cnt_T \times v_T\) 是 \(v_S\) 的倍数，那我们只需要把所有的 \(T\) 物品换成 \(\frac{cnt_T \times v_T}{v_S}\) 个 \(S\) 物品即可。

所以，\(cnt_T\) 的上界为 \(\text{lcm}(v_T, v_S) / v_T\)，再拿多就不优了。由于 \(\text{lcm}(v_T, v_S) \le v_T \times v_S\)，同理可以计算出少拿 \(S\) 物品的个数的上界，因此枚举上界不会超过 \(10^4\)。

然后就做完了。时间复杂度 \(O(n k\log V)\)。\(k\) 是单组枚举上界，不超过 \(10^4\)；\(V\) 是二分价值的值域，不超过 \(10^9\)。

（我赛时更豪放一点，\(k\) 开到了 \(10^5\)）

code :

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef double db;
const int N = 110;
int a[N], b[N], c[N], d[N], n;
ll X;

ll get(ll i, ll x) {
    db c1 = b[i] * 1.0 / a[i], c2 = d[i] * 1.0 / c[i];
    if(c1 > c2) swap(a[i], c[i]), swap(b[i], d[i]);
    ll cnt1 = (x + a[i] - 1) / a[i], res = 1e18;
    int k = 0;
    while(~cnt1 && k <= 100000) {
        ll cnt2 = (max(0ll, x - cnt1 * a[i]) + c[i] - 1) / c[i];
        res = min(res, cnt1 * b[i] + cnt2 * d[i]);
        cnt1--;
        k++;
    }
    return res;
}
bool chk(ll mid) {
    ll res = 0;
    for (int i = 1; i <= n; i++) res += get(i, mid);
    return res <= X;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> X;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
    ll l = 0, r = 1e9;
    while(l < r) {
        ll mid = (l + r + 1) / 2;
        if(chk(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l;
    return 0;
}