CSP-X2024山东小学组T4：刷题

题目链接

CSP-X2024山东小学组T4：刷题

题目描述

比赛之路多艰，做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩，小红就是这样的人。
为了继续提升自己的编程实力，小红整理了一份刷题题单，并选中了题单中的 $n$ 道编程题，将它们从 $1$ 到 $n$ 编号，计划用 $m$ 天时间按照题目编号顺序做完所有的题目（一道题目只能在同一天完成，不可以使用多天完成同一道题目）。

在小红的计划中，她完成第 $i$ 道题目的时间为 $a_i$。因为题目有难有易，小红做题时可以找好朋友小明帮忙解题，通过询问小明一道题目的解法，可以省去这个题目的做题时间。当然了，小红做题是为了提升自己，而不是提升小明。因此小红决定一天最多求助小明一次。

本题 $m$ 天中，小红做题时间最长一天的总耗时定义为 $T$（小明帮忙做的题目不计入小红的做题总时间）。请你帮小红求出 $T$ 的最小值是多少？

输入格式

第一行两个正整数 $n$，$m$，分别表示小红要做的题目数和计划用的天数。
第二行 $n$ 个正整数，分别表示每个题目解题所用时间 $a_i$。

输出格式

输出仅一行，表示 $m$ 天中耗时最长一天的总耗时 $T$ 的最小值。

样例 #1

样例输入 #1

4 2
1 2 3 3

样例输出 #1

3

样例 #2

样例输入 #2

3 4
999 999 999

样例输出 #2

0

提示

30% 的数据，$n\le 1000$；
60% 的数据，$n\le 10,000$；
100% 的数据，$n\le 100,000$，$0\le a_i\le 10,000$，$1\le m\le 1000$。

算法思想

根据题目描述，要在$m$天里按顺序完成$n$道题，并且每天都可以求助小明帮忙解决一道题，求做题时间最长的一天总耗时$T$的最小值，显然可以用二分查找来解决。

那么如何判断二分的结果$mid$是否满足要求呢？这里可以用贪心的思想，在一天中做题时间不超过$mid$的情况下，尽可能的多做题，不妨设$cnt$天能把$n$道题做完，当$cnt\le m$时满足要求。

除此之外，对于小明来说，显然要去解决每一天中耗时最长的那道题。

时间复杂度

最坏情况下，在$1$天里把所有题做完，那么最小值$T=n\times a_i$，那么时间复杂度为：$O(n\times logT)$

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int n, m, a[N];
bool check(LL mid)
{
    int cnt = 1, maxx = a[1]; //统计每天里耗时最长的题目所用时间
    LL sum = a[1]; //统计一天里做题的总时间
    for(int i = 2; i <= n; i ++)
    {
        maxx = max(maxx, a[i]); //求一天里耗时最长的题目所用时间
        if(sum + a[i] - maxx <= mid) sum += a[i]; //如果一天的做题时间不超过mid，那么就再做一题
        else
        {
            cnt ++; //需要的天数增加
            sum = a[i]; 
            maxx = a[i];
        }
    }
    return cnt <= m; //当做完n道题的天数不超过时，满足要求
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    LL L = 0, R = 1e10; //最坏情况在1天把n道题做完，因此R=n*a[i]
    while(L < R)
    {
        LL mid = (L + R) / 2;
        if(check(mid)) R = mid;
        else L = mid + 1;
    }
    cout << L << endl;
}