2555. 两个线段获得的最多奖品

Powered by:NEFU AB-IN

Link

2555. 两个线段获得的最多奖品

题意

在 X轴 上有一些奖品。给你一个整数数组 prizePositions ，它按照 非递减 顺序排列，其中 prizePositions[i] 是第 i 件奖品的位置。数轴上一个位置可能会有多件奖品。再给你一个整数 k 。

你可以同时选择两个端点为整数的线段。每个线段的长度都必须是 k 。你可以获得位置在任一线段上的所有奖品（包括线段的两个端点）。注意，两个线段可能会有相交。

比方说 k = 2 ，你可以选择线段 [1, 3] 和 [2, 4] ，你可以获得满足 1 <= prizePositions[i] <= 3 或者 2 <= prizePositions[i] <= 4 的所有奖品 i 。
请你返回在选择两个最优线段的前提下，可以获得的 最多 奖品数目。

思路

1. 枚举右维护左
   看到两个线段（或者两个别的，类比两数之和）的问题，想到这个思路，对右边的线段进行枚举，然后维护左边的线段。题目要求覆盖尽可能多的礼物，那么两个线段不相交，尽可能多的覆盖是最优的

   1. 枚举右线段的右端点，通过二分，求出最远可以到达的左端点
   2. 左端点往左的区间，就是第一个线段存在的区间了，那么我们需要求出 [0, r] 中选出一个长度为k的线段，最多覆盖多少礼物，记为dp[r]
   3. 这个dp值是可以边求边算的，当我们枚举第二个线段时，我们就知道了以这个右端点为端点的覆盖礼物数量，但是我们也可以不选这个右端点，那么dp值就是 max(dp[r - 1], r - l + 1)
   4. 这样我们左侧的线段就不用枚举考虑，直接取dp值即可

2. 前后缀分解
   遇到分成两个区间的，想到前后缀分解，也就是选择一个分界点，分成前面和后面两部分，前面选一个线段，后面选一个线段即可

   1. 和之前思路一样，不过这里求单个线段礼物最大数为：使用滑动窗口技术来计算这个数组，具体是遍历 prizePositions，维护一个窗口 [i, j]，确保 prizePositions[j] - prizePositions[i] 不超过 k，更新前缀最大值数组
   2. 然后计算dp值，还是选与不选的问题
   3. 前缀数组 prefix 记录了从左到右可以获得的最大奖品数（通过一个长度为 k 的线段），后缀数组 suffix 记录了从右到左可以获得的最大奖品数，后缀计算 (flag = -1)：当 flag = -1 时，表示我们在反向（从右到左）计算。
      在这种情况下，数组 prizePositions 被反转，窗口的长度也需要调整
   4. 枚举分界点即可，前面dp加上后面dp取最大

代码

class Solution:def maximizeWin(self, prizePositions: List[int], k: int) -> int:n = len(prizePositions)dp = [0] * (n + 1)ans = 0for i in range(n):x = bisect.bisect_left(prizePositions, prizePositions[i] - k)ans = max(ans, i - x + 1 + dp[x])dp[i + 1] = max(dp[i], i - x + 1)return ans

class Solution:def maximizeWin(self, prizePositions: List[int], k: int) -> int:n = len(prizePositions)def calc(flag: int):prefix = Arr.array(0, n + 1)i = 0for j in range(n):while flag * (prizePositions[j] - prizePositions[i]) > k:i += 1# 选与不选prefix[j + 1] = Math.max(prefix[j], j - i + 1)return prefixprefix = calc(1)prizePositions = prizePositions[::-1]suffix = calc(-1)ans = 0for i in range(n + 1):ans = Math.max(ans, prefix[i] + suffix[n - i])return ans