Python程序：最大化提升K个子列表后的最小值

假设我们有一个名为nums的数字列表和两个值size和k。现在假设有一个操作，我们取一个长度为size的连续子列表并将每个元素加一。我们可以执行此操作k次，我们必须找到nums中可能的最大最小值。

因此，如果输入类似于nums = [2, 5, 2, 2, 7]，size = 3，k = 2，则输出将为3，因为我们可以将[2, 5, 2]增加到[3, 6, 3, 2, 7]，然后将[6, 3, 2]增加到[3, 7, 4, 3, 7]，最小值为3

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数possible()。这将接收目标值target。
• events := 一个大小为N的列表，并填充0
• moves := 0, s := 0
• 对于范围0到N的i，执行：
  • s := s + events[i]
  • delta := target -(A[i] + s)
  • 如果delta > 0，则
    • moves := moves + delta
    • s := s + delta
    • 如果i + size < N，则
      • events[i + size] := events[i + size] - delta
• 当moves <= K时返回true
• 从主方法中执行以下操作：
• N := A的大小
• left := 0, right := 10^10
• 当left < right时，执行：
  • mid :=(left + right + 1) / 2
  • 如果possible(mid)为真，则
    • left := mid
  • 否则，
    • right := mid - 1
• 返回left

让我们看看下面的实现以更好地理解：

示例

 在线演示

class Solution:
   def solve(self, A, size, K):
      N = len(A)
   def possible(target):
      events = [0] * N
      moves = s = 0
      for i in range(N):
         s += events[i]
         delta = target - (A[i] + s)
         if delta > 0:
            moves += delta
            s += delta
            if i + size < N:
               events[i + size] -= delta
               return moves <= K
               left, right = 0, 10 ** 10
               while left < right:
                  mid = (left + right + 1)//2
               if possible(mid):
                  left = mid
               else:
                  right = mid - 1
      return left
ob = Solution()
nums = [2, 5, 2, 2, 7]
size = 3
k = 2
print(ob.solve(nums, size, k))

输入

[2, 5, 2, 2, 7], 3, 2

输出

3

Arnab Chakraborty

更新于：2020年10月19日

182 次浏览

开启您的职业生涯

完成课程获得认证

开始学习