fork()==0世界线变动

3049. 标记所有下标的最早秒数 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：

```txt

输入：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：

```txt

输入：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：

```txt

输入：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

778. 水位上升的泳池中游泳

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

示例 1:

```txt

输入: grid = [[0,2],[1,3]]

输出: 3

解释:

时间为0时，你位于坐标方格的位置为 (0, 0)。

此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

```

示例 2:

```txt

输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]

输出: 16

解释: 最终的路线用加粗进行了标记。

我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

```

提示:

• n == grid.length

• n == grid[i].length

• 1 <= n <= 50

• 0 <= grid[i][j] < n^2

• grid[i][j] 中每个值 均无重复

6367. 求出最多标记下标

给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

• 选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。

请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。

示例 1：

```txt

输入：nums = [3,5,2,4]

输出：2

解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。

没有其他更多可执行的操作，所以答案为 2 。

```

示例 2：

```txt

输入：nums = [9,2,5,4]

输出：4

解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。

第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。

没有其他更多可执行的操作，所以答案为 4 。

```

示例 3：

```txt

输入：nums = [7,6,8]

输出：0

解释：没有任何可以执行的操作，所以答案为 0 。

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

878. 第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。

示例 1：

```txt

输入：n = 1, a = 2, b = 3

输出：2

```

示例 2：

```txt

输入：n = 4, a = 2, b = 3

输出：6

```

提示：

• 1 <= n <= 10^9

• 2 <= a, b <= 4 * 10^4

6355. 统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且

• lower <= nums[i] + nums[j] <= upper

示例 1：

```txt

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6

输出：6

解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

```

示例 2：

```txt

输入：nums = [1,7,9,2,5], lower = 11, upper = 11

输出：1

解释：只有单个公平数对：(2,3) 。

```

提示：

• 1 <= nums.length <= 10^5

• nums.length == n

• -10^9 <= nums[i] <= 10^9

• -10^9 <= lower <= upper <= 10^9

2250. 统计包含每个点的矩形数目

给你一个二维整数数组 rectangles ，其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 高为 hi 。给你一个二维整数数组 points ，其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。

第 i 个矩形的 左下角 在 (0, 0) 处，右上角 在 (li, hi) 。

请你返回一个整数数组 count ，长度为 points.length，其中 count[j]是 包含 第 j 个点的矩形数目。

如果 0 <= xj <= li 且 0 <= yj <= hi ，那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。

示例 1：

```txt

输入：rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]

输出：[2,1]

解释：

第一个矩形不包含任何点。

第二个矩形只包含一个点 (2, 1) 。

第三个矩形包含点 (2, 1) 和 (1, 4) 。

包含点 (2, 1) 的矩形数目为 2 。

包含点 (1, 4) 的矩形数目为 1 。

所以，我们返回 [2, 1] 。

```

示例 2：

```txt

输入：rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]

输出：[1,3]

解释：

第一个矩形只包含点 (1, 1) 。

第二个矩形只包含点 (1, 1) 。

第三个矩形包含点 (1, 3) 和 (1, 1) 。

包含点 (1, 3) 的矩形数目为 1 。

包含点 (1, 1) 的矩形数目为 3 。

所以，我们返回 [1, 3] 。

```

提示：

• 1 <= rectangles.length, points.length <= 5 * 10^4

• rectangles[i].length == points[j].length == 2

• 1 <= li, xj <= 10^9

• 1 <= hi, yj <= 100

• 所有 rectangles 互不相同 。

• 所有 points 互不相同 。

1760. 袋子里最少数目的球

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。

  • 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

```txt

输入：nums = [9], maxOperations = 2

输出：3

解释：

• 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。

• 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。

装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

```

示例 2：

```txt

输入：nums = [2,4,8,2], maxOperations = 4

输出：2

解释：

• 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。

• 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。

• 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。

• 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。

装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

```

示例 3：

```txt

输入：nums = [7,17], maxOperations = 2

输出：7

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= maxOperations, nums[i] <= 10^9