Pythonでペアワイズ隣接和を小さくするプログラム

numsなどの非負の数と非負の値kのリストがあるとします。ここで、numsで1つの正のアンバーを選択し、それを1減らす操作を実行できると仮定します。リスト内の隣接する値のすべてのペアの合計が<=kになるように、必要な操作の最小数を見つける必要があります。答えが非常に大きい場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がnums =[4、6、2、5]、k =6のような場合、リストを[3、3、1、4]にデクリメントできるため、出力は5になります。 5デクリメントの。ここで、隣接するすべてのペアの合計は<=6です。

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7
• ans：=0
• 範囲0からnums-1のサイズのiの場合、do
  • sm：=nums [i] + nums [i + 1]
  • diff：=smの最大値-kおよび0
  • nums [i + 1]：=nums [i + 1] --diff
  • nums [i + 1] <0の場合、
    • nums [i + 1]：=0
  • ans：=ans + diff
• return ans mod m

理解を深めるために、次の実装を見てみましょう-

例

m = 10 ** 9 + 7
class Solution:
   def solve(self, nums, k):
      ans = 0
      for i in range(0, len(nums) - 1):
         sm = nums[i] + nums[i + 1]
         diff = max(sm - k, 0)
         nums[i + 1] -= diff
         if nums[i + 1] < 0:
            nums[i + 1] = 0
         ans += diff
      return ans % m
ob = Solution()
nums = [4, 6, 2, 5]
k = 6 print(ob.solve(nums, k))

入力

[4, 6, 2, 5], 6

出力

5