2024-08-14：用 go 语言，给定两个长度分别为 n 和 m 的整数数组 nums 和 changeIndices，下标从 1 开始。初始时，nums 中所有下标均未标记。从第 1 秒到第 m 秒，每秒可以选择以下四种操

作者：福大大架构师每日一题

2024-08-14
北京
本文字数：1578 字
阅读完需：约 5 分钟

2024-08-14：用 go 语言，给定两个长度分别为 n 和 m 的整数数组 nums 和 changeIndices，下标从 1 开始。初始时，nums 中所有下标均未标记。

从第 1 秒到第 m 秒，每秒可以选择以下四种操作之一：

1.选择范围 [1, n] 中一个下标 i，将 nums[i]减少 1。

2.将 nums[changeIndices[s]]设为任意非负整数。

3.选择范围 [1, n] 中一个下标 i，标记满足 nums[i]为 0 的下标 i。

4.不执行任何操作。

任务是找到最早的秒数（在范围 [1, m] 中），在这个秒数下执行最佳操作后，能够标记所有下标。如果无法标记所有下标，返回-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 。

答案 2024-08-14：

chatgpt

题目来自 leetcode3049。

大体步骤如下：

1.初始化总秒数为数组 nums 的长度 n，并遍历 nums 计算出总共需要的天数 total（慢速复习 + 考试）。

2.创建一个数组 firstT，用于记录每个索引对应的首次变化的时间（从 m 开始往前）。

3.初始化堆 h，并利用 sort.Search 函数找到最小的秒数 ans，使得满足能够标记所有下标。

4.在排序后的时间线上依次进行操作，首先检查是否需要继续慢速复习或考试，然后根据条件进行相应的操作，更新堆 h 并维护慢速复习天数以及快速复习（堆中的元素）。

5.如果所有下标被标记，则返回最早秒数 ans；否则返回 -1。

总的时间复杂度为 O(m log m)（sort.Search 的二分查找）+ O(m)（遍历整个时间线）= O(m log m)

总的额外空间复杂度为 O(m)（堆 h 的存储空间）。

go 完整代码如下：

package main
import (  "container/heap"  "fmt"  "sort")
func earliestSecondToMarkIndices(nums, changeIndices []int) int {  n, m := len(nums), len(changeIndices)  if n > m {    return -1  }
  total := n  for _, v := range nums {    total += v // 慢速复习+考试所需天数  }
  firstT := make([]int, n)  for t := m - 1; t >= 0; t-- {    firstT[changeIndices[t]-1] = t + 1  }
  h := hp{}  ans := n + sort.Search(m+1-n, func(mx int) bool {    mx += n    cnt, slow := 0, total    h.IntSlice = h.IntSlice[:0]    for t := mx - 1; t >= 0; t-- {      i := changeIndices[t] - 1      v := nums[i]      if v <= 1 || t != firstT[i]-1 {        cnt++ // 留给左边，用来快速复习/考试        continue      }      if cnt == 0 {        if h.Len() == 0 || v <= h.IntSlice[0] {          cnt++ // 留给左边，用来快速复习/考试          continue        }        slow += heap.Pop(&h).(int) + 1        cnt += 2 // 反悔：一天快速复习，一天考试      }      slow -= v + 1      cnt-- // 快速复习，然后消耗一天来考试      heap.Push(&h, v)    }    return cnt >= slow // 剩余天数搞定慢速复习+考试  })  if ans > m {    return -1  }  return ans}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }func (h *hp) Pop() any   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func main() {  nums := []int{3, 2, 3}  changeIndices := []int{1, 3, 2, 2, 2, 2, 3}  fmt.Println(earliestSecondToMarkIndices(nums, changeIndices))}