7. LCP 12.小张刷题计划(中等，题目条件没读仔细)
思想
1.为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。
在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。
我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。
2.因为有按照题目编号顺序就直接贪心即可，无需再考虑其他的，我原来在思考贪心不能保证最优解，没有必要
3.二分答案为最多一天耗时，而该值越小，越不满足条件，所以存在一个最小值，而一旦一个值满足条件，大于它的值也一定满足条件
代码
c++:
class Solution {
public:
bool check(vector<int>& time, int m, int mid) {
int cnt = 1, sum = 0, maxval = 0;
for (const int t : time) {
// 先判断条件再相应更新
// 两种情况:t是最大值或t不是最大值
if ((t > maxval && sum <= mid) || sum + t - maxval <= mid) {
sum += t;
maxval = max(maxval, t);
} else {
++cnt;
if (cnt > m)
return false;
sum = t;
maxval = t;
}
}
return true;
}
int minTime(vector<int>& time, int m) {
bool t = check(time, m, 3);
int n = time.size();
if (n <= m)
return 0;
int left = INT_MAX, right = 0, res = 0;
for (const int t : time) {
left = min(left, t);
right += t;
}
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(time, m, mid)) {
res = mid;
right = mid - 1;
} else
left = mid + 1;
}
return res;
}
};
学习模拟逻辑:
bool check(vector<int>& time, int m, int mid) {
int cnt = 1, sum = 0, maxval = 0;
for (const int t : time) {
// 先加再判断是否超出条件，超出条件再更新
sum += t;
maxval = max(maxval, t);
if (sum - maxval > mid) {
++cnt;
if (cnt > m)
return false;
sum = t;
maxval = t;
}
}
return true;
}
2.5 最大化最小值
本质是二分答案求最大。二分的 mid 表示下界。
1.套路
c++:
2.题目描述
1(学习).给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。
你需要选择 n 个整数(存在即可)，其中第 i 个整数必须属于第 i 个区间(条件1)。所选整数的 得分 定义为所选整数两两之间的 最小 绝对差(条件，即二分答案一定小于任意绝对值之差)。
返回所选整数的 最大可能得分(答案) 。
3.学习经验
(1)
1. 3281.范围内整数的最大得分(中等,学习，题意有点绕)
3281. 范围内整数的最大得分 - 力扣（LeetCode）
思想
1.给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。
你需要选择 n 个整数(存在即可)，其中第 i 个整数必须属于第 i 个区间。所选整数的 得分 定义为所选整数两两之间的 最小 绝对差。
返回所选整数的 最大可能得分 。
2.这题的条件不是很明确，但二分答案是可能得分，即最小绝对差，所以去找两两之间的绝对差，如果都大于等于选取的score,说明score找小了，但说明满足条件(注意：这里是至少，不是恰好，两数之差的最小值可以不等于 score。由于二分会不断缩小范围，最终一定会缩小到任意两数之差的最小值恰好等于 score 的位置上,细品)，如果有一个小于score，则说明找大了，不满足条件，所以score有一个最大值，满足单调性
3.首先对区间左端点排序(经验)，利用贪心策略查找，因为题目只要存在组整数，让两两绝对值之差都大于score即可，所以要让两两绝对值之差尽可能地大，所以一开始选左端点x[0]，会出现以下两种情况:
x[i]+score>start[i]+d,说明score取大了，即说明存在一个绝对值之差小于score,即score不满足条件x[i]+score<start[i]或者x[i]+score>=start[i] && x[i]+score<=start[i]+d,这两种情况都满足条件，但为了保证整数在区间内，所以取x=max(x+score,start[i])
为了0元素方便取，让一开始的x为INT_MIN,所以一开始的x肯定取start[0]
4.这种情况先不要先想证明单调性检验，先假设有一个二分答案score,然后分类讨论情况，判断什么时候符合条件，什么时候不符合条件，自然就能得出满不满足单调性了
代码
c++:
class Solution {
public:
bool check(vector<int>& start, int d, int mid) {
int x = INT_MIN;
for (const int t : start) {
x = max(x + mid, t);
if (x > t + d)
return false;
}
return true;
}
int maxPossibleScore(vector<int>& start, int d) {
sort(start.begin(), start.end());
int left = 0, right = INT_MAX, res = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(start, d, mid)) {
res = mid;
left = mid + 1;
} else
right = mid - 1;
}
return res;
}
};