5562. 最大生产

$ WA 代码$

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

const int N = 100010;
int a[N], b[N];

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &b[i]);
    }
    //O(kn) -> O(log(kn))
    int cnt = b[0] / a[0];
    for(int j = 1; j < n; j ++ ){
        cnt = min(cnt, b[j] / a[j]);
    }
    for(int t = 0; t < n; t ++ ){
        b[t] -= (long long) cnt * a[t];
    }
    while(k > 0){
        for(int u = 0; u < n; ){
            if(b[u] >= a[u]) u ++ ;
            else{
                k -= (a[u] - b[u]);
                b[u] = 0;
            }
            if(k <= 0) break;
        }
        if(k > 0) cnt ++ ;
    }
    printf("%d", cnt);
    return 0;
}

分析：

在最坏情况下，总复杂度大致是 $O((\frac{k}{a_{min}} + 1) \times n)$（$a_{min}$为数组 $a$ 中元素的最小值），最大计算次数为 $10^{14}$，远远超过 $10^{8}$，不难想到需要将代码优化到含 $\log$ 的复杂度，就是说该用二分了。

$ AC 代码$

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

const int N = 100010;
int a[N], b[N];
int n, k;

bool check(int x) {
    LL need = 0, cur = 0; // need：需要的原材料总数；cur：当前种类的材料花费
    for (int i = 0; i < n; i++) {
        cur = (LL)a[i] * x; //强制类型转换：防止等号右边的乘积超过int最大值
        if (cur > b[i]) {
            need += (cur - b[i]);   // 这里有没有括号都无所谓，但如果比赛的时候不是特别清楚的话还是加上吧
        }
        if (need > k) return false; // 如果所需原材料超过了k，则不能生产x辆修蹄车
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }

    int l = 0, r = 2e9; // 修蹄车数量可能的范围
    while (l < r) {
        int mid = l + (r - l + 1) / 2; // 向上取整避免死循环
        if (check(mid)) l = mid; // 如果可以生产mid辆修蹄车，则尝试增加
        else r = mid - 1; // 否则减少尝试的数量
    }

    printf("%d\n", l);
    return 0;
}

分析：

这段代码的时间复杂度为 $O(n logC)$，其中 $C$ 是二分查找范围的上限，这里为 $2e9$，即 $2 \times 10^9$。此时代码排除了 $k$ 的影响，最大计算次数为 $3 \times 10^6 $，效率大大地提高了（喜）！

下面分析二分是怎么实现的：

首先，代码使用了左上型（左真型 & 向上取整）。原因很简单，题中要求的是最大值，故采用左真型；而在逼近答案时 l 和 r 是会相邻的，为避免死循环，采用向上取整。

其次，看搜索范围。l 从 0 开始很显然，而 r 的值则需假设数据以判断最大可能的数量，由题意得 r 初值为 2e9。

最后，写 check 函数，框架有 2 种：
（1）默认返回 false，而在满足特定条件时返回 true；或默认返回 true，而在满足特定条件时返回 false。（一般情况下都用这种框架，根据题意选择默认返回谁）
（2）返回一个条件表达式，根据表达式的真假对应返回 true 和 false。（check函数逻辑较简单时用这种框架）

这里使用了第一种框架，具体实现看原代码。