本文主要是介绍【教3妹学编程-算法题】标记所有下标的最早秒数 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3妹：2哥2哥，你有没有看到上海女老师出轨男学生的瓜啊。
2哥 : 看到 了，真的是太毁三观了！
3妹：是啊， 老师本是教书育人的职业，明确规定不能和学生谈恋爱啊，更何况是出轨。
2哥 : 是啊，更何况男生才16，年龄也不匹配啊。
3妹：2哥高中时有早恋吗，2哥最早谈恋爱是什么时候鸭？
2哥：切，又拿我单身狗开玩笑了。
3妹：说到最早，我今天看到一个关于“最早”的题目，让我们一起来做下吧~
题目：
给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。
一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。
从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：
选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
将 nums[changeIndices[s]] 设置成任意的 非负 整数。
选择范围 [1, n] 中的一个下标 i ， 满足 nums[i] 等于 0, 并 标记 下标 i 。
什么也不做。
请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。
示例 1：
输入：nums = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
输出：6
解释：这个例子中，我们总共有 7 秒。按照以下操作标记所有下标：
第 1 秒：将 nums[changeIndices[1]] 变为 0 。nums 变为 [0,2,3] 。
第 2 秒：将 nums[changeIndices[2]] 变为 0 。nums 变为 [0,2,0] 。
第 3 秒：将 nums[changeIndices[3]] 变为 0 。nums 变为 [0,0,0] 。
第 4 秒：标记下标 1 ，因为 nums[1] 等于 0 。
第 5 秒：标记下标 2 ，因为 nums[2] 等于 0 。
第 6 秒：标记下标 3 ，因为 nums[3] 等于 0 。
现在所有下标已被标记。
最早可以在第 6 秒标记所有下标。
所以答案是 6 。
示例 2：
输入：nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
输出：7
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
第 1 秒：标记下标 1 ，因为 nums[1] 等于 0 。
第 2 秒：标记下标 2 ，因为 nums[2] 等于 0 。
第 3 秒：将 nums[4] 减少 1 。nums 变为 [0,0,1,1] 。
第 4 秒：将 nums[4] 减少 1 。nums 变为 [0,0,1,0] 。
第 5 秒：将 nums[3] 减少 1 。nums 变为 [0,0,0,0] 。
第 6 秒：标记下标 3 ，因为 nums[3] 等于 0 。
第 7 秒：标记下标 4 ，因为 nums[4] 等于 0 。
现在所有下标已被标记。
最早可以在第 7 秒标记所有下标。
所以答案是 7 。
示例 3：
输入：nums = [1,2,3], changeIndices = [1,2,3]
输出：-1
解释：这个例子中，无法标记所有下标，因为我们没有足够的秒数。
所以答案是 -1 。
提示：
1 <= n == nums.length <= 5000
0 <= nums[i] <= 10^9
1 <= m == changeIndices.length <= 5000
1 <= changeIndices[i] <= n
思路：
题意是：
你可以在任意一天完成一门课程的考试（前提是复习完成）。考试这一天不能复习。
搞定所有课程的复习+考试，至少要多少天？
提示 1
答案越大，越能够搞定所有课程，反之越不能。
有单调性，可以二分答案。
提示 2
如果决定在第 i 天快速复习第 changeIndices[i]门课程，那么在第 i天前慢速复习这门课程是没有意义的。同理，如果决定慢速复习某门课程，那么也没必要对这门课程使用快速复习。
java代码：
class Solution {public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {int n = nums.length;int m = changeIndices.length;if (n > m) {return -1;}long slow = n; // 慢速复习+考试所需天数for (int v : nums) {slow += v;}int[] firstT = new int[n];Arrays.fill(firstT, -1);for (int t = m - 1; t >= 0; t--) {firstT[changeIndices[t] - 1] = t;}PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);int left = n - 1, right = m + 1;while (left + 1 < right) {pq.clear();int mid = (left + right) / 2;if (check(nums, changeIndices, firstT, pq, slow, mid)) {right = mid;} else {left = mid;}}return right > m ? -1 : right;}private boolean check(int[] nums, int[] changeIndices, int[] firstT, PriorityQueue<Integer> pq, long slow, int mx) {int cnt = 0;for (int t = mx - 1; t >= 0; t--) {int i = changeIndices[t] - 1;int v = nums[i];if (v <= 1 || t != firstT[i]) {cnt++; // 留给左边，用来快速复习/考试continue;}if (cnt == 0) {if (pq.isEmpty() || v <= pq.peek()) {cnt++; // 留给左边，用来快速复习/考试continue;}slow += pq.poll() + 1;cnt += 2; // 反悔：一天快速复习，一天考试}slow -= v + 1;cnt--; // 快速复习，然后消耗一天来考试pq.offer(v);}return cnt >= slow; // 剩余天数不能慢速复习+考试}
}
这篇关于【教3妹学编程-算法题】标记所有下标的最早秒数 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
