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

更新於：2020年10月19日

182 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告