题解：B4107 [CSP-X2024 山东] 刷题

_miss_ · 2024-12-30 14:38:43 · 题解

B4107 [CSP-X2024 山东] 刷题

注意到答案有单调性，考虑二分答案，二分做题时间。

check 函数思路：

先求出目前的最大值，贪心的给小明做最难的题，如果超出了做题的最大值，这一天就不做了，如果其中一天做完了，就返回 1，否则返回 0。

update on 2025.7.7 修改了 mid 的计算错误。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[N];
// 检查在给定的时间限制下是否可以完成任务
bool check(int x) {
    // 表示已经使用的天数
    int c = 1;
    // 表示当前任务的索引
    int s = 1;
    // 循环直到所有任务都被分配
    while (s <= n) {
        // 初始化变量t，表示当前天的总耗时
        int t = 0;
        // 初始化变量mx，表示当前天的最大耗时
        int mx = 0;
        // 循环直到当前天的总耗时超过给定的时间限制或所有任务都被分配
        int i;
        for (i = s; i <= n; i++) {
            // 更新当前天的最大耗时
            mx = max(mx, a[i]);
            // 检查是否可以将当前任务分配到当前天
            if (t + a[i] - mx <= x) {
                // 如果可以，将当前任务分配到当前天
                t += a[i];
            } else {
                // 如果不能，跳出循环
                break;
            }
        }
        // 更新当前任务的索引
        s = i;
        // 如果所有任务都被分配，跳出循环
        if (s > n) break;
        // 增加已经使用的天数
        c++;
    }
    // 检查是否可以在给定的天数内完成任务
    return c <= m;
}
int main() {
    // 好习惯 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        r += a[i];
    }
    // 初始化变量ans，表示最小的最大耗时
    int ans = r;
    // 循环直到找到最小的最大耗时
    while (l <= r) {
        // 计算中间值
        int mid = l + (r - l) / 2;// 好习惯 
        // 检查是否可以在中间值的时间限制下完成任务
        if (check(mid)) {
            // 如果可以，更新最小的最大耗时和时间限制的范围
            ans = mid;
            r = mid - 1;
        } else {
            // 如果不能，更新时间限制的范围
            l = mid + 1;
        }
    }
    // 输出最小的最大耗时
    cout << ans << "\n";
    return 0;
}