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

Giả sử chúng ta có một mảng với các số nguyên gọi là nums, chúng ta cũng có hai giá trị khác m và k. Bây giờ, chúng ta cần làm m bó hoa. Để làm một bó hoa, chúng ta cần k hoa liền kề trong vườn. Ở đây khu vườn bao gồm n bông hoa khác nhau, bông hoa thứ i sẽ nở vào ngày [i]. Mỗi bông hoa chỉ có thể được sử dụng bên trong một bó hoa. Chúng ta phải tìm số ngày tối thiểu cần phải chờ để tạo ra m bó hoa từ khu vườn. Nếu chúng ta không thể làm m bó hoa, hãy trả về -1.

Vì vậy, nếu đầu vào giống như bloomDay =[5,5,5,5,10,5,5] m =2 k =3, thì đầu ra sẽ là 10 vì chúng ta cần 2 (m =2) bó hoa và mỗi bó hoa nên có 3 bông hoa.

• Sau ngày thứ 5:[x, x, x, x, _, x, x], chúng ta có thể làm một bó trong số ba bông đầu tiên đã nở, nhưng không thể làm một bó khác

• Sau ngày thứ 10:[x, x, x, x, x, x, x], Bây giờ chúng ta có thể làm hai bó hoa theo nhiều cách khác nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của bloomDay

• nếu m * k> n, thì

  • trả về -1

• Xác định một hàm khả thi (). Điều này sẽ mất x

• đếm:=0, bó hoa:=0

• cho mỗi ngày trong bloomDay, làm

  • nếu d <=x thì

    • count:=count + 1

    • nếu số đếm giống như k, thì

      • bó hoa:=bó hoa + 1

      • đếm:=0

  • nếu không,

    • đếm:=0

• trả về true nếu bó hoa> =m, ngược lại là false

• Từ phương thức chính, hãy làm như sau -

• left:=0, right:=1 + tối đa của bloomDay

• trong khi trái

  • giữa:=(trái + phải) / 2

  • nếu có thể (giữa) là đúng, thì

    • right:=mid

  • nếu không,

    • left:=mid + 1

• nếu có thể (trái) là đúng, thì

  • quay lại bên trái

• nếu không thì quay lại trái + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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