LeetCode 题解 | 力扣杯 LCP 12.小张刷题计划
点击上方蓝字关注我们
下面开始今天的学习~
题目描述
为了提高自己的代码能力,小张制定了
LeetCode
刷题计划,他选中了 LeetCode
题库中的 n
道题,编号从 0
到 n-1
,并计划在 m
天内 按照题目编号顺序 刷完所有的题目(注意,小张不能用多天完成同一题)。在小张刷题计划中,小张需要用
time[i]
的时间完成编号 i
的题目。此外,小张还可以使用场外求助功能,通过询问他的好朋友小杨题目的解法,可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”,小张每天最多使用一次求助。我们定义
m
天中做题时间最多的一天耗时为 T
(小杨完成的题目不计入做题总时间)。请你帮小张求出最小的T
是多少。示例 1:
输入:
time = [1,2,3,3], m = 2
输出:
3
解释:第一天小张完成前三题,其中第三题找小杨帮忙;第二天完成第四题,并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间,并且这个值是最小的。
示例 2:
输入:
time = [999,999,999], m = 4
输出:
0
解释:在前三天中,小张每天求助小杨一次,这样他可以在三天内完成所有的题目并不花任何时间。
限制:
1 <= time.length <= 10^5
1 <= time[i] <= 10000
1 <= m <= 1000
解决方案
题意概述
给定一个数组,将其划分成 M 份,使得每份元素之和最大值最小,每份可以任意减去其中一个元素。
题解
如果不考虑每份可以任意减去一个元素,就是一个经典的二分问题,具有单调最优的性质:如果最大值为 t 可以满足条件划分,那么最大值为 t + 1 也可以。所以就直接二分最大值 t,找到最小满足条件的 t 即可。
本题加了一个条件:每份可以删除任意一个数组。为了能够让最大值最小,显然每份中删去的一定是最大元素,所以在二分判定可行性时,维护当前序列的最大值,然后记录删除最大值的结果,也就是说二分的判定是:是否可以让每组删除最大值之后,总和都小于等于 t。
C++ 实现
classSolution {
public:
boolCheck(int limit, vector<int> cost, int day){
// 每组划分 limit 的最大和,贪心划分看有多少组
int useday, totaltime, maxtime;
useday = 1; totaltime = maxtime = 0;
for (int i=0; i<cost.size(); ++i) {
int nexttime = min(maxtime, cost[i]);
if (nexttime + totaltime <= limit) {
totaltime += nexttime;
maxtime = max(maxtime, cost[i]);
} else {
++useday;
totaltime = 0;
maxtime = cost[i];
}
}
return (useday <= day);
}
intminTime(vector<int>& time, int m){
int left, right, middle;
left = right = 0;
for (int i=0; i<time.size(); ++i) {
right += time[i];
}
while (left <= right) {
middle = (left + right) >> 1;
if (Check(middle, time, m)) right = middle - 1;
else left = middle + 1;
}
return left;
}
};
Python 实现
classSolution:
defminTime(self, time: List[int], m: int) -> int:
l,r = 0,sum(time)
while l<r:
mid = (l+r)1
ifself.check(mid,time,m):
r = mid
else:
l = mid + 1
return l
defcheck(self, limit, cost, day):
use_day,total_time,max_time = 1,0,cost[0]
for i in cost[1:]:
if total_time+min(max_time,i)<= limit:
total_time,max_time = total_time+min(max_time,i),max(max_time,i)
else:
use_day += 1
total_time,max_time = 0,i
return use_day<=day
复杂度分析
时间复杂度:O(N log M),其中 N 是数组的大小,M 是数组所有元素之和。
空间复杂度:O(N)。
BY /
本文作者:力扣
编辑&版式:霍霍
声明:本文归“力扣”版权所有,如需转载请联系。
推荐阅读
关键词
元素
最大值
题解
题目
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。