โปรแกรมค้นหาระนาบพื้นที่ขั้นต่ำที่จำเป็นสำหรับนักกระโดดร่มใน k วันใน python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums ซึ่งแต่ละค่าแสดงถึงกลุ่มคนที่มองหาการกระโดดร่มด้วยกัน และเรามีค่า k อีกค่าหนึ่งซึ่งแทนจำนวนวันที่พวกเขาสามารถกระโดดร่มได้ เราต้องค้นหาความจุขั้นต่ำของเครื่องบินที่เราจำเป็นต้องทำตามคำขอทั้งหมดภายใน k วัน คำขอควรดำเนินการตามลำดับที่ได้รับและเครื่องบินสามารถบินได้วันละครั้งเท่านั้น

ดังนั้น หากอินพุตเป็น nums =[16, 12, 18, 11, 13], k =3 เอาต์พุตจะเป็น 28 เนื่องจากเครื่องบิน 28 คนสามารถจัดกลุ่มคำขอที่กำหนดโดย [16, 12], [ 18], [11, 13].

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

• ถ้า nums ว่างเปล่าก็
  • คืน 0
• เริ่มต้น :=สูงสุดของ nums สิ้นสุด :=ผลรวมขององค์ประกอบทั้งหมดของ nums
• ขณะเริ่ม <สิ้นสุด ทำ
  • กลาง :=(เริ่มต้น + สิ้นสุด) / 2
  • วัน :=1, อุณหภูมิ :=0
  • สำหรับแต่ละ num เป็น nums ทำ
    • ถ้า temp + num> mid แล้ว
      • วัน :=วัน + 1
      • อุณหภูมิ :=num
    • มิฉะนั้น
      • อุณหภูมิ :=อุณหภูมิ + num
  • ถ้าวัน> k แล้ว
    • เริ่ม :=กลาง + 1
  • มิฉะนั้น
    • จบ :=กลาง
• คืนเริ่ม

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0

      start, end = max(nums), sum(nums)

      while start < end:
         mid = (start + end) // 2

         days = 1
         temp = 0
         for num in nums:
            if temp + num > mid:
               days += 1
               temp = num
            else:
               temp += num

         if days > k:
            start = mid + 1
         else:
            end = mid

      return start

ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))

อินพุต

[16, 12, 18, 11, 13], 3

ผลลัพธ์

28