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完整代码如下：
packagemain
import(
"container/heap"
"fmt"
"sort"
)
funcearliestSecondToMarkIndices(nums,changeIndices[]int)int{
n,m:=len(nums),len(changeIndices)
ifn>m{
return-1
}
total:=n
for_,v:=rangenums{
total+=v//慢速复习+考试所需天数
}
firstT:=make([]int,n)
fort:=m-1;t>=0;t--{
firstT[changeIndices[t]-1]=t+1
}
h:=hp{}
ans:=n+sort.Search(m+1-n,func(mxint)bool{
mx+=n
cnt,slow:=0,total
h.IntSlice=h.IntSlice[:0]
fort:=mx-1;t>=0;t--{
i:=changeIndices[t]-1
v:=nums[i]
ifv<=1||t!=firstT[i]-1{
cnt++//留给左边，用来快速复习/考试
continue
}
ifcnt==0{
ifh.Len()==0||v<=h.IntSlice[0]{
cnt++//留给左边，用来快速复习/考试
continue
}
slow+=heap.Pop(&h).(int)+1
cnt+=2//反悔：一天快速复习，一天考试
}
slow-=v+1
cnt--//快速复习，然后消耗一天来考试
heap.Push(&h,v)
}
returncnt>=slow//剩余天数搞定慢速复习+考试
})
ifans>m{
return-1
}
returnans
}
typehpstruct{sort.IntSlice}
func(h*hp)Push(vany){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];returnv}
funcmain(){
nums:=[]int{3,2,3}
changeIndices:=[]int{1,3,2,2,2,2,3}
fmt.Println(earliestSecondToMarkIndices(nums,changeIndices))
}
热门跟贴