Pythonでのk回の操作後に可能な最小値を見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとします。ここで、リスト内の任意の要素から1を引くことができる操作について考えてみましょう。この操作はk回実行できます。このような操作をk回行​​った後、リストから可能な最小の最大値を見つける必要があります。

したがって、入力がnums =[3、4、6、5] k =6のような場合、出力は3になります。これは、4を1回、6を3回、5を2回減らして、[3,3,3、 3]。

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

• 番号を逆の順序で並べ替えます
• i：=0
• curr：=nums [0]
• k> 0の場合、do
  • i
  • i：=i + 1
• k> =iの場合、
  • k：=k-i
  • curr：=curr-1
• それ以外の場合、
  • リターンカー

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

例

class Solution:
   def solve(self, nums, k):
      nums.sort(reverse=True)
      i = 0
      curr = nums[0]
      while k > 0:
         while i < len(nums) and nums[i] == curr:
            i += 1
         if k >= i:
            k -= i
            curr -= 1
         else:
            return curr
      return curr

ob = Solution()
nums = [3, 4, 6, 5]
k = 6
print(ob.solve(nums, k))

入力

[3, 4, 6, 5], 6

出力

3