题面描述

为了提升软件编码能力，小王制定了刷题计划。他选了题库中的 $n$ 道题，编号从 $0$ 到 $n-1$，并计划在 $m$ 天内按照题目编号顺序刷完所有的题目（注意，小王不能用多天完成同一题）。

在小王刷题计划中，小王需要用 time[i] 的时间完成编号 $i$ 的题目。

此外，小王还可以查看答案，可以省去该题的做题时间。为了真正达到刷题效果，小王每天最多直接看一次答案。

我们定义 $m$ 天中做题时间最多的一天耗时为 $T$ （直接看答案的题目不计入做题总时间）。

请你帮小王求出最小的 $T$ 是多少。

思路

本题可以看作是在给定的 $m$ 天内，将题目按顺序分配到每一天，每天可以选择跳过最多一个题目（即不花费时间完成），目标是最小化所有天中做题时间的最大值 $T$。

为了求解这个问题，可以采用二分查找结合贪心算法的策略：

1. 二分查找范围：$T$ 的范围在 $0$ 到所有题目时间的总和之间。
2. 判断函数：对于给定的 $T$，判断是否可以在 $m$ 天内完成所有题目，使得每一天的做题时间（跳过一个题目后的总时间）不超过 $T$。
   • 在判断过程中，每天尽可能多地安排题目，允许跳过一个题目（通常选择当天耗时最大的题目跳过），以确保当天的总做题时间不超过 $T$。
3. 更新二分范围：如果可以在 $m$ 天内完成，则尝试更小的 $T$；否则，尝试更大的 $T$。

关键点

• 每一天最多跳过一个题目：这意味着在每一天的题目分配中，我们可以选择一个题目不计入当天的总耗时。
• 选择跳过最大的题目：为了最小化当天的总耗时，应该选择当天耗时最大的题目跳过。
• 特殊情况处理：
  • 当 $m \geq n$ 时，可以将每个题目分配到单独的一天，并选择跳过所有题目，使得 $T=0$。
  • 当某个题目的时间非常大时，需要确保通过跳过来控制当天的总耗时。

判断函数 canFinish 的实现

对于给定的 $T$，我们需要判断是否可以将所有题目分配到 $m$ 天内，使得每一天跳过一个题目后的总耗时不超过 $T$。具体步骤如下：

1. 初始化：

   • days = 1：开始分配第一天。
   • current_sum = 0：当前天的总耗时。
   • current_max = 0：当前天的最大题目耗时。

2. 遍历所有题目：

   • 将当前题目的时间加到 current_sum。
   • 更新 current_max 为当天已分配题目中的最大值。
   • 如果 current_sum - current_max > T，说明需要开始新的一天：
     • days += 1
     • 将当前题目分配到新的一天，重置 current_sum 和 current_max 为当前题目的时间。

3. 最终判断：

   • 如果分配的天数 days 不超过 m，则当前的 $T$ 是可行的；否则，不可行。

cpp

#include <bits/stdc++.h>
using namespace std;

// 判断是否可以在 m 天内完成所有题目，且每一天的做题时间（跳过一个题目后） <= T
bool canFinish(const vector<long long>& time, int m, long long T) {
    int days = 1;            // 开始的天数
    long long current_sum = 0;  // 当前天的总耗时
    long long current_max = 0;  // 当前天的最大题目耗时

    for(auto t : time){
        current_sum += t;
        current_max = max(current_max, t);

        // 如果跳过当天最大题目后的总耗时超过 T，需开始新的一天
        if(current_sum - current_max > T){
            days++;
            current_sum = t;    // 新一天从当前题目开始
            current_max = t;    // 重置当天最大耗时
        }
    }
    return days <= m;
}

int main(){
    string s;
    getline(cin, s);
    // 解析 time 数组
    vector<long long> time;
    string num = "";
    for(char c : s){
        if(c == ',') {
            if(!num.empty()){
                time.push_back(stoll(num));
                num = "";
            }
        }
        else{
            num += c;
        }
    }
    if(!num.empty()) time.push_back(stoll(num));
    
    int m;
    cin >> m;
    
    int n = time.size();
    
    // 特殊情况处理：如果 m >= n，可以跳过所有题目，T=0
    if(m >= n){
        cout << "0";
        return 0;
    }
    
    // 二分查找最小的 T
    long long left = 0;
    long long right = 0;
    for(auto t : time) right += t; // 最大可能的 T
    
    long long answer = right;
    while(left <= right){
        long long mid = left + (right - left)/2;
        if(canFinish(time, m, mid)){
            answer = mid;
            right = mid -1;
        }
        else{
            left = mid +1;
        }
    }
    cout << answer;
}

python

def can_finish(time, m, T):
    days = 1            # 开始的天数
    current_sum = 0     # 当前天的总耗时
    current_max = 0     # 当前天的最大题目耗时

    for t in time:
        current_sum += t
        current_max = max(current_max, t)

        # 如果跳过当天最大题目后的总耗时超过 T，需开始新的一天
        if current_sum - current_max > T:
            days +=1
            current_sum = t    # 新一天从当前题目开始
            current_max = t    # 重置当天最大耗时
    return days <=m

def main():
    import sys
    import sys
    s = sys.stdin.readline().strip()
    while s == '':
        s = sys.stdin.readline().strip()
    time = list(map(int, s.split(',')))
    m_line = sys.stdin.readline().strip()
    while m_line == '':
        m_line = sys.stdin.readline().strip()
    m = int(m_line)
    
    n = len(time)
    if m >=n:
        print(0)
        return
    
    left =0
    right = sum(time)
    answer = right
    while left <= right:
        mid = (left + right)//2
        if can_finish(time, m, mid):
            answer = mid
            right = mid -1
        else:
            left = mid +1
    print(answer)

if __name__ == "__main__":
    main()

java

import java.util.*;
public class Main {
    // 判断是否可以在 m 天内完成所有题目，且每一天的做题时间（跳过一个题目后） <= T
    public static boolean canFinish(long[] time, int m, long T){
        int days =1;                // 开始的天数
        long current_sum =0;        // 当前天的总耗时
        long current_max =0;        // 当前天的最大题目耗时

        for(long t : time){
            current_sum += t;
            current_max = Math.max(current_max, t);
            
            // 如果跳过当天最大题目后的总耗时超过 T，需开始新的一天
            if(current_sum - current_max > T){
                days++;
                current_sum = t;    // 新一天从当前题目开始
                current_max = t;    // 重置当天最大耗时
            }
        }
        return days <=m;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = "";
        while(s.isEmpty()){
            if(sc.hasNextLine()){
                s = sc.nextLine().trim();
            }
            else{
                break;
            }
        }
        String[] parts = s.split(",");
        long[] time = new long[parts.length];
        for(int i=0;i<parts.length;i++) time[i] = Long.parseLong(parts[i]);
        int m = sc.nextInt();
        
        int n = time.length;
        // 特殊情况处理：如果 m >= n，可以跳过所有题目，T=0
        if(m >=n){
            System.out.println("0");
            return;
        }
        
        long left =0;
        long right =0;
        for(long t : time) right += t; // 最大可能的 T
        long answer = right;
        while(left <= right){
            long mid = left + (right - left)/2;
            if(canFinish(time, m, mid)){
                answer = mid;
                right = mid -1;
            }
            else{
                left = mid +1;
            }
        }
        System.out.println(answer);
    }
}

题目内容

为了提升软件编码能力，小王制定了刷题计划，他选了题库中的n道题，编号从 $0$ 到 $n-1$ ，并计划在 $m$ 天内按照题目编号顺序刷完所有的题目（注意，小王不能用多天完成同一题）。

在小王刷题计划中，小王需要用 $tme[i]$ 的时间完成编号 $i$ 的题目。

此外，小王还可以查看答案，可以省去该题的做题时间。为了真正达到刷题效果，小王每天最多直接看一次答案。

我们定义 $m$ 天中做题时间最多的一天耗时为 $T$ （直接看答案的题目不计入做题总时间)。

请你帮小王求出最小的 $T$ 是多少。

输入描述

第一行输入为 $time$，$time[i]$ 的时间完成编号 $i$ 的题目

第二行输入为 $m$ ，$m$ 表示几天内完成所有题目，$1 ≤ m ≤ 180$

输出描述

最小耗时整数 $T$

样例1

输入

999,999,999
4

输出

0

说明

在前三天中，小王每天都直接看答案，这样他可以在三天内完成所有的题目并不花任何时间

样例2

输入

1,2,2,3,5,4,6,7,8
5

输出

4

说明

第一天完成前 $3$ 题，第 $3$ 题看答案;

第二天完成第 $4$ 题和第 $5$ 题，第 $5$ 题看答案；

第三天完成第 $6$ 和第 $7$ 题，第 $7$ 提看答案;

第四天完成第 $8$ 题，直接看答案；

第五天完成第 $9$ 题，直接看答案。