Chương trình tìm số ngày tối thiểu để làm m bó hoa bằng Python

Cho mảng bloomDay, bloomDay[i] là ngày hoa i nở. Cần làm m bó, mỗi bó cần k hoa liền kề. Mỗi hoa chỉ dùng cho 1 bó. Tìm ngày nhỏ nhất để có thể làm đủ m bó. Không thể thì trả về -1.

Ví dụ: bloomDay = [5,5,5,5,10,5,5], m = 2, k = 3. Ngày 5: [x,x,x,x,_,x,x] chỉ làm 1 bó. Ngày 10: tất cả nở → làm 2 bó. Kết quả 10.

Thuật toán giải quyết (Tìm kiếm nhị phân)

• Nếu m*k > n: trả về -1.
• Hàm possible(x): kiểm tra xem đến ngày x có làm được ≥ m bó không.
  • Duyệt bloomDay, đếm hoa nở liên tiếp (count). Khi count == k: bouquets++, count=0. Gặp hoa chưa nở: count=0.
• Tìm kiếm nhị phân left=0, right=max(bloomDay)+1. Tìm left nhỏ nhất sao cho possible(left) = True.

Ví dụ triển khai

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))

Đầu vào

[5,5,5,5,10,5,5], 2, 3

Đầu ra

10