#P3221. 编码能力提升计划(200分)
-
1000ms
Tried: 95
Accepted: 25
Difficulty: 6
所属公司 :
华为od
编码能力提升计划(200分)
题面描述
为了提升软件编码能力,小王制定了刷题计划。他选了题库中的 n 道题,编号从 0 到 n−1,并计划在 m 天内按照题目编号顺序刷完所有的题目(注意,小王不能用多天完成同一题)。
在小王刷题计划中,小王需要用 time[i] 的时间完成编号 i 的题目。
此外,小王还可以查看答案,可以省去该题的做题时间。为了真正达到刷题效果,小王每天最多直接看一次答案。
我们定义 m 天中做题时间最多的一天耗时为 T (直接看答案的题目不计入做题总时间)。
请你帮小王求出最小的 T 是多少。
思路
本题可以看作是在给定的 m 天内,将题目按顺序分配到每一天,每天可以选择跳过最多一个题目(即不花费时间完成),目标是最小化所有天中做题时间的最大值 T。
为了求解这个问题,可以采用二分查找结合贪心算法的策略:
- 二分查找范围:T 的范围在 0 到所有题目时间的总和之间。
- 判断函数:对于给定的 T,判断是否可以在 m 天内完成所有题目,使得每一天的做题时间(跳过一个题目后的总时间)不超过 T。
- 在判断过程中,每天尽可能多地安排题目,允许跳过一个题目(通常选择当天耗时最大的题目跳过),以确保当天的总做题时间不超过 T。
- 更新二分范围:如果可以在 m 天内完成,则尝试更小的 T;否则,尝试更大的 T。
关键点
- 每一天最多跳过一个题目:这意味着在每一天的题目分配中,我们可以选择一个题目不计入当天的总耗时。
- 选择跳过最大的题目:为了最小化当天的总耗时,应该选择当天耗时最大的题目跳过。
- 特殊情况处理:
- 当 m≥n 时,可以将每个题目分配到单独的一天,并选择跳过所有题目,使得 T=0。
- 当某个题目的时间非常大时,需要确保通过跳过来控制当天的总耗时。
判断函数 canFinish 的实现
对于给定的 T,我们需要判断是否可以将所有题目分配到 m 天内,使得每一天跳过一个题目后的总耗时不超过 T。具体步骤如下:
-
初始化:
days = 1:开始分配第一天。current_sum = 0:当前天的总耗时。current_max = 0:当前天的最大题目耗时。
-
遍历所有题目:
- 将当前题目的时间加到
current_sum。 - 更新
current_max为当天已分配题目中的最大值。 - 如果
current_sum - current_max > T,说明需要开始新的一天:days += 1- 将当前题目分配到新的一天,重置
current_sum和current_max为当前题目的时间。
- 将当前题目的时间加到
-
最终判断:
- 如果分配的天数
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 题,直接看答案。