สมมติว่าเรามีอาร์เรย์ bloomDay, m และ k เราต้องทำ m ช่อดอกไม้ แต่ละช่อต้องการ k ดอกที่ติดกัน ดอกไม้ที่ i จะบานในวันที่ bloomDay[i] แต่ละดอกใช้ได้เพียง 1 ช่อ หาจำนวนวันน้อยที่สุดที่ต้องรอเพื่อทำ m ช่อ ถ้าทำไม่ได้คืน -1
เช่น bloomDay = [5,5,5,5,10,5,5] m = 2 k = 3 ผลลัพธ์คือ 10
- วันที่ 5: [x,x,x,x,_,x,x] ทำได้ 1 ช่อ (3 ดอกแรก) แต่นำดอกที่ 5 ยังไม่บาน ทำช่อที่ 2 ไม่ได้
- วันที่ 10: [x,x,x,x,x,x,x] ทำได้ 2 ช่อ
ขั้นตอนการแก้ปัญหา
- n = len(bloomDay)
- ถ้า m * k > n: คืน -1 (ดอกไม้ไม่พอ)
- สร้างฟังก์ชัน possible(x) ตรวจสอบว่าใน x วันทำ m ช่อได้ไหม:
- count = 0, bouquets = 0
- วนลูป d ใน bloomDay:
- ถ้า d ≤ x: count += 1; ถ้า count == k: bouquets += 1; count = 0
- มิฉะนั้น: count = 0 (ดอกไม่ติดกัน)
- คืน bouquets ≥ m
- Binary search: left = 0, right = max(bloomDay) + 1
- while left < right: mid = (left + right) // 2; ถ้า possible(mid): right = mid มิฉะนั้น left = mid + 1
- ถ้า possible(left): คืน left มิฉะนั้น left + 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
