ABC374E | 小学数学题？

· · 题解

省流：二分+小学数学

注意到 N \le 100 和 A_i,B_i \le 100，这个数据范围比较小，很可能与时间复杂度有关。

题目要求 \displaystyle W=\min_{i=1}^N W_i 的最大值，看到最小值最大，果断二分。于是思路就出来了：二分 W，看能否用 X 的预算达到。

具体来讲，二分 W，对于第 i 轮加工，我们要使 W_i \ge W，也就是找到这样的 a_i,b_i，使得 W_i = a_iA_i+b_iB_i \ge W 且 \sum_{i=1}^N a_iP_i+b_iQ_i \le X。

要想不超过预算，花费就得尽可能少，也就是要使 a_iP_i+b_iQ_i 最小，同时要让 a_iA_i+b_iB_i \ge W。这不禁让人想起小学数学题：

有一群人要租车。有小客车、大客车。怎样租车最便宜？

这种问题烦人之处在于，有的时候你不仅要选最划算的车，还要让座位的利用率高（我反正只会凑答案……）。购入机器也是一样的。但是每种机器购入多少台呢？

这就引出本题的一个结论：第 i 轮加工的两种机器中，必有一种的购入数量少于另一种的单台机器产量。

换句话说，如果你主要购入 S_i，那么你购入的 T_i 的数量少于 A_i。反之亦然。

这是因为，每当你购入 B_i 台 S_i 或 A_i 台 T_i，你都会获得 A_iB_i 的产量。而对于相同的 A_iB_i 的产量，为使花费最少，一定只会选择两种方案中更便宜的那一种（也就是 \min(B_iP_i,A_iQ_i)）。所以，当你主要购入 S_i 的时候（此时 B_iP_i \le A_iQ_i），每当你购入 A_i 台 T_i，你都可以将其换成更优的 B_i 台 S_i。

那么我们直接在二分里面枚举 S_i 或 T_i 的数量，取花费最小值即可。

代码如下：

#include <bits/stdc++.h>
#define int long long
#define N 105
using namespace std;
int a[N], b[N], p[N], q[N], n, X;
bool check(int x) {
    int sum = 0;  //达到x生产容量的最小花费 
    for(int i = 1; i <= n; i++) {
        int res = 1e15;   //寻找最小花费 
        for(int j = 0; j < a[i]; j++) {
            //枚举主要购买Si时，购入的Ti数量 
            if(j*b[i] > x) break;
            int tmp = x-j*b[i];
            res = min(res, j*q[i]+(tmp+a[i]-1)/a[i]*p[i]);
        }
        for(int j = 0; j < b[i]; j++) {
            //枚举主要购买Ti时，购入的Si数量 
            if(j*a[i] > x) break;
            int tmp = x-j*a[i];
            res = min(res, j*p[i]+(tmp+b[i]-1)/b[i]*q[i]);
        }
        sum += res;
    }
    return sum <= X; 
}
signed main() {
    cin >> n >> X;
    for(int i = 1; i <= n; i++) cin >> a[i] >> p[i] >> b[i] >> q[i];
    int l = 0, r = 1e10, mid;   //二分W（上界差不多1e9吧） 
    while(l <= r) {
        mid = (l + r) >> 1;
        if(check(mid)) l = mid+1;
        else r = mid-1;
    }
    cout << l-1;
    return 0;
}