class Solution {
public:
int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
}
};
100200. 标记所有下标的最早秒数 I
给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。
一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。
从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：
[1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。nums[changeIndices[s]] 等于 0 ，标记 下标 changeIndices[s] 。请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。
示例 1：
输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1] 输出：8 解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标： 第 1 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [1,2,0] 。 第 2 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,2,0] 。 第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,1,0] 。 第 4 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,0,0] 。 第 5 秒，标记 changeIndices[5] ，也就是标记下标 3 ，因为 nums[3] 等于 0 。 第 6 秒，标记 changeIndices[6] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。 第 7 秒，什么也不做。 第 8 秒，标记 changeIndices[8] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。 现在所有下标已被标记。 最早可以在第 8 秒标记所有下标。 所以答案是 8 。
示例 2：
输入：nums = [1,3], changeIndices = [1,1,1,2,1,1,1] 输出：6 解释：这个例子中，我们总共有 7 秒。按照以下操作标记所有下标： 第 1 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,2] 。 第 2 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,1] 。 第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,0] 。 第 4 秒：标记 changeIndices[4] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。 第 5 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,0] 。 第 6 秒：标记 changeIndices[6] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。 现在所有下标已被标记。 最早可以在第 6 秒标记所有下标。 所以答案是 6 。
示例 3：
Input: nums = [0,1], changeIndices = [2,2,2] Output: -1 Explanation: 这个例子中，无法标记所有下标，因为下标 1 不在 changeIndices 中。 所以答案是 -1 。
提示：
1 <= n == nums.length <= 20000 <= nums[i] <= 1091 <= m == changeIndices.length <= 20001 <= changeIndices[i] <= n原站题解
golang 解法, 执行用时: 11 ms, 内存消耗: 6 MB, 提交时间: 2024-02-26 10:29:54
// 二分 + 逆向思维
func earliestSecondToMarkIndices(nums []int, changeIndices []int) int {
var (
n = len(nums)
m = len(changeIndices)
ans int
)
//特判剪枝
if n > m {
return -1
}
//二分答案
markLastIdx := make([]int, n) // markLastIdx[i] 需标记i的最迟时间/changeIndices下标
ans = sort.Search(m+1, func(mx int) bool { // 注意数组下标从1开始
//初始化 markLastIdx
for i := 0; i < n; i++ {
markLastIdx[i] = -1
}
for i, markIdx := range changeIndices[:mx] {
markIdx-- // 因下标从1开始
markLastIdx[markIdx] = i
}
//在mx时间内，有下标根本标记不到，直接false
if slices.Contains(markLastIdx, -1) {
return false
}
//依据markLastIdx看在mx时间内能否标记全部
var idleTime int // 闲置可用时间
for i, markIdx := range changeIndices[:mx] {
markIdx--
if i == markLastIdx[markIdx] { // 当前时间必须要去标记nums[markIdx]了
if idleTime < nums[markIdx] { // 闲置可用时间不足以标记此下标
return false
}
idleTime -= nums[markIdx]
} else {
idleTime++
}
}
return true
})
if ans == m+1 {
return -1
}
return ans
}
python3 解法, 执行用时: 77 ms, 内存消耗: 17 MB, 提交时间: 2024-02-26 10:15:46
class Solution:
def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
# 对nums每个元素先清零，再对changeIndices做标记
def check(t: int) -> bool:
idxs = set() # 存储逆向操作时已被“取标记”的下标
need = 0
for curt in range(t-1,-1,-1):
idx = changeIndices[curt]-1
if idx not in idxs:
idxs.add(idx) # curt时刻标记，肯定不亏
need+=nums[idx] # 再往前的时刻的减1操作就可以分给这个下标用了，不属于浪费
else:
need=max(0,need-1)
return need==0 and len(idxs)==len(nums) # 为了实现简洁，没有判断答案下限，所以这里判断一下是不是真的所有下标都清零了
if not check(len(changeIndices)): return -1 # 无解
return bisect_left(range(len(changeIndices)+1), 1, key=check)