标记所有下标的最早秒数 II

100197. 标记所有下标的最早秒数 II

给你两个下标从 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⁹
1 <= m == changeIndices.length <= 5000
1 <= changeIndices[i] <= n

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) { } };

golang 解法, 执行用时: 10 ms, 内存消耗: 6.2 MB, 提交时间: 2024-02-26 10:44:02

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 = h[: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 len(h) == 0 || v <= h[0].v {
					cnt++ // 留给左边，用来快速复习/考试
					continue
				}
				slow += heap.Pop(&h).(pair).v + 1
				cnt += 2 // 反悔：一天快速复习，一天考试
			}
			slow -= v + 1
			cnt-- // 快速复习，然后消耗一天来考试
			heap.Push(&h, pair{v, i})
		}
		return cnt >= slow // 剩余天数不能慢速复习+考试
	})
	if ans > m {
		return -1
	}
	return ans
}

type pair struct{ v, i int }
type hp []pair
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

java 解法, 执行用时: 4 ms, 内存消耗: 43.9 MB, 提交时间: 2024-02-26 10:36:33

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<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        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<int[]> 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()[0]) {
                    cnt += 1; // 留给左边，用来快速复习/考试
                    continue;
                }
                slow += pq.poll()[0] + 1;
                cnt += 2; // 反悔：一天快速复习，一天考试
            }
            slow -= v + 1;
            cnt--; // 快速复习，然后消耗一天来考试
            pq.offer(new int[]{v, i});
        }
        return cnt >= slow; // 剩余天数不能慢速复习+考试
    }
}

python3 解法, 执行用时: 55 ms, 内存消耗: 17.6 MB, 提交时间: 2024-02-26 10:34:35

# 二分，类比成先复习再考试
class Solution:
    def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:
        n, m = len(nums), len(changeIndices)
        total = n + sum(nums)

        first_t = [-1] * n
        for t in range(m - 1, -1, -1):
            first_t[changeIndices[t] - 1] = t

        def check(mx: int) -> bool:
            cnt = 0
            slow = total  # 慢速复习+考试所需天数
            h = []
            for t in range(mx - 1, -1, -1):
                i = changeIndices[t] - 1
                v = nums[i]
                if v <= 1 or t != first_t[i]:
                    cnt += 1  # 留给左边，用来快速复习/考试
                    continue
                if cnt == 0:
                    if not h or v <= h[0][0]:
                        cnt += 1  # 留给左边，用来快速复习/考试
                        continue
                    slow += heappop(h)[0] + 1
                    cnt += 2  # 反悔：一天快速复习，一天考试
                slow -= v + 1
                cnt -= 1  # 快速复习，然后消耗一天来考试
                heappush(h, (v, i))
            return cnt >= slow  # 剩余天数不能慢速复习+考试

        ans = n + bisect_left(range(n, m + 1), True, key=check)
        return -1 if ans > m else ans

上一题

下一题

详情