Pythonで最小グループの可能な最大値を見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとします。リストをk個の連続したグループに分割する必要があります。最小のグループは、すべてのグループの中で合計が最小のグループです。したがって、最小のグループの可能な最大値を見つけます。

したがって、入力がnums =[2、6、4、5、8] k =3のような場合、リストを[2、6]、[4]のように3つのグループに分割できるため、出力は8になります。 、5]、[8]。したがって、最小グループの合計は8になります。

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

• 関数is_divisible（）を定義します。これはターゲットになります

• ターゲットが<=1の場合、

  • Trueを返す

• num_chunks：=0、current_sum：=0

• numsのxごとに、実行します

  • current_sum：=current_sum + x

  • current_sum> =targetの場合、

    • current_sum：=0

    • num_chunks：=num_chunks + 1

    • num_chunksがkと同じ場合、

      • Trueを返す

• Falseを返す

• メインの方法から、次のようにします-

• 左：=1

• right：=（numsのすべての要素の合計）/ k + 1

• 左<右-1、実行

  • mid：=（左+右）/ 2

  • is_divisible（mid）がtrueの場合、

    • 左：=中央

  • それ以外の場合

    • 右：=半ば

• 左に戻る

例（Python）

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

class Solution:
   def solve(self, nums, k):
      def is_divisible(target):
         if target <= 1:
            return True
         num_chunks = 0
         current_sum = 0
         for x in nums:
            current_sum += x
            if current_sum >= target:
               current_sum = 0
               num_chunks += 1
               if num_chunks == k:
                  return True
         return False
      left = 1
      right = sum(nums) // k + 1
      while left < right - 1:
         mid = (left + right) // 2
         if is_divisible(mid):
            left = mid
         else:
            right = mid
      return left
ob = Solution()
nums = [2, 6, 4, 5, 8]
k = 3
print(ob.solve(nums, k))

入力

[2, 6, 4, 5, 8], 3

出力

8