สมมติว่าเรามีอาร์เรย์ที่มีจำนวนเต็มเรียกว่า nums เราก็มีค่าอีกสองค่า m และ k ตอนนี้เราต้องทำช่อดอกไม้ ในการทำหนึ่งช่อเราต้องการ k ดอกไม้ที่อยู่ติดกันจากสวน ที่นี่สวนประกอบด้วยดอกไม้ที่แตกต่างกัน n ดอกไม้จะบานสะพรั่งวัน[i] แต่ละดอกสามารถใช้ได้ภายในช่อเดียวเท่านั้น เราต้องหาจำนวนวันขั้นต่ำที่ต้องรอเพื่อทำช่อมจากสวน หากเราไม่สามารถจัดช่อได้ ให้คืน -1
ดังนั้นหากอินพุตเป็นเหมือน bloomDay =[5,5,5,5,10,5,5] m =2 k =3 ผลลัพธ์จะเป็น 10 เพราะเราต้องการช่อดอกไม้ 2 (m =2) และแต่ละอันควร มี 3 ดอก
-
หลังจากวันที่ 5:[x, x, x, x, _, x, x] เราสามารถทำช่อดอกไม้จากสามดอกแรกที่บานได้ 1 ช่อ แต่ไม่สามารถทำช่ออื่นได้
-
หลังจากวันที่ 10:[x, x, x, x, x, x, x] ตอนนี้เราสามารถทำช่อดอกไม้สองช่อด้วยวิธีต่างๆ กัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ bloomDay
-
ถ้า m * k> n แล้ว
-
กลับ -1
-
-
กำหนดฟังก์ชั่นที่เป็นไปได้ () นี่จะใช้เวลา x
-
จำนวน :=0, ช่อดอกไม้ :=0
-
สำหรับแต่ละ d ใน bloomDay ทำ
-
ถ้า d <=x แล้ว
-
นับ :=นับ + 1
-
ถ้าการนับเท่ากับ k แล้ว
-
ช่อ :=ช่อ + 1
-
นับ :=0
-
-
-
มิฉะนั้น
-
นับ :=0
-
-
-
คืนค่า จริง หากช่อ>=m มิฉะนั้น เท็จ
-
จากวิธีหลักให้ทำดังต่อไปนี้ -
-
ซ้าย :=0, ขวา :=1 + สูงสุด BloomDay
-
ขณะที่ซ้าย <ขวา ทำ
-
กลาง :=(ซ้าย + ขวา) /2
-
ถ้าเป็นไปได้ (กลาง) เป็นจริงแล้ว
-
ขวา :=กลาง
-
-
มิฉะนั้น
-
ซ้าย :=กลาง + 1
-
-
-
ถ้าเป็นไปได้ (ซ้าย) เป็นจริงแล้ว
-
กลับซ้าย
-
-
มิฉะนั้นกลับซ้าย + 1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(bloomDay, m, k): n = len(bloomDay) if m * k > n: return -1 def possible(x): count = 0 bouquets = 0 for d in bloomDay: if d <= x: count += 1 if count == k: bouquets += 1 count = 0 else: count = 0 return bouquets >= m left, right = 0, max(bloomDay) + 1 while left < right: mid = (left + right)//2 if possible(mid): right = mid else: left = mid + 1 if possible(left): return left else: return left + 1 bloomDay = [5,5,5,5,10,5,5] m = 2 k = 3 print(solve(bloomDay, m, k))
อินพุต
[5,5,5,5,10,5,5], 2, 3
ผลลัพธ์
10
