โปรแกรมหาค่าสูงสุดของกลุ่มที่เล็กที่สุดใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องแยกรายการออกเป็น k กลุ่มที่อยู่ติดกัน กลุ่มที่เล็กที่สุดคือกลุ่มที่มีผลรวมน้อยที่สุดจากทุกกลุ่ม ดังนั้นจงหาค่าสูงสุดที่เป็นไปได้ของกลุ่มที่เล็กที่สุด

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 6, 4, 5, 8] k =3 ผลลัพธ์จะเป็น 8 เนื่องจากเราสามารถแบ่งรายการออกเป็นสามกลุ่ม เช่น [2, 6], [4 , 5], [8]. ดังนั้นกลุ่มขั้นต่ำจึงมีผลรวม 8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน is_divisible() นี้จะเป็นเป้าหมาย

• ถ้าเป้าหมาย <=1 แล้ว

  • คืนค่า True

• num_chunks :=0, current_sum :=0

• สำหรับแต่ละ x เป็นตัวเลข ทำ

  • current_sum :=current_sum + x

  • ถ้า current_sum>=เป้าหมาย แล้ว

    • current_sum :=0

    • num_chunks :=num_chunks + 1

    • ถ้า num_chunks เหมือนกับ k แล้ว

      • คืนค่า True

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ซ้าย :=1

• right :=(ผลรวมของธาตุทั้งหมดเป็น nums) / k + 1

• ขณะที่ซ้าย <ขวา - 1 ทำ

  • กลาง :=(ซ้าย + ขวา) / 2

  • ถ้า is_divisible(mid) เป็นจริง

    • ซ้าย :=กลาง

  • มิฉะนั้น

    • ขวา :=กลาง

• กลับซ้าย

ตัวอย่าง (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