Chương trình kiểm tra xem chúng ta có thể ăn kẹo yêu thích vào ngày yêu thích của chúng ta hay không bằng Python

Giả sử chúng ta có một mảng candyCount dương trong đó candyCount [i] biểu thị số lượng kẹo thuộc loại thứ i mà chúng ta có. Chúng ta cũng có một mảng khác được gọi là truy vấn trong đó các truy vấn [i] có ba tham số [favourite_i, favouriteDay_i, dailyCap_i]. Chúng tôi có một số quy tắc:

• Chúng tôi bắt đầu ăn kẹo vào ngày thứ 0.

• Chúng ta không thể ăn bất kỳ loại kẹo nào thuộc loại i trừ khi chúng ta đã ăn tất cả các loại kẹo thuộc loại i-1 trước đó.

• Chúng ta phải ăn ít nhất một viên kẹo mỗi ngày cho đến khi ăn hết chúng.

Duy trì các quy tắc này, chúng ta phải tạo một mảng giá trị Boolean cho mỗi kết quả truy vấn và mục nhập thứ i là true nếu chúng ta có thể ăn một viên kẹo loại favouriteType_i vào ngày favouriteDay_i mà không ăn nhiều hơn dailyCap_i kẹo vào bất kỳ ngày nào. Chúng ta có thể ăn nhiều loại kẹo khác nhau trong cùng một ngày, theo quy tắc 2.

Vì vậy, nếu đầu vào giống như candyCount =[7,4,5,3,8], truy vấn =[[0,2,2], [4,2,4], [2,13,100]], thì đầu ra sẽ là [true, false, true] bởi vì

• Nếu chúng ta ăn 2 viên kẹo loại 0 vào ngày 0 và ngày 1, chúng ta sẽ ăn một viên kẹo loại 0 vào ngày

• Chúng ta có thể ăn nhiều nhất 4 viên kẹo mỗi ngày. Nếu chúng ta ăn 4 viên kẹo mỗi ngày, chúng ta sẽ ăn 4 viên kẹo loại 0 vào ngày 0 và 4 viên kẹo loại 0, loại 1 vào ngày 1. Sau đó đến ngày thứ 2, chúng ta chỉ được ăn 4 viên loại 1, loại 2. kẹo, vì vậy chúng ta không thể ăn kẹo loại 4 vào ngày thứ 2.

• Chúng ta có thể ăn 1 viên kẹo mỗi ngày, chúng ta sẽ ăn một viên kẹo loại 2 vào ngày thứ 13.

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

• sumcandy:=một danh sách với một phần tử duy nhất là candyCount [0]

• chỉ mục:=1

• trong khi chỉ mục

  • insert (sumcandy [index-1] + candyCount [index]) vào cuối sumcandy

  • index:=index + 1

• chèn 0 vào cuối sumcandy

• res:=một danh sách mới

• cho mỗi truy vấn, hãy thực hiện

  • typ:=each [0]

  • ngày:=mỗi [1]

  • cap:=each [2]

  • nếu day + 1> sumcandy [typ] hoặc (day + 1) * cap <=sumcandy [typ-1], thì

    • chèn False vào cuối res

  • nếu không,

    • chèn True vào cuối res

• trả lại res

Ví dụ

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

def solve(candiesCount, queries):
   sumcandy = [candiesCount[0]]
   index=1
   while index < len(candiesCount):
      sumcandy.append(sumcandy[index-1] + candiesCount[index])
      index+=1
   sumcandy.append(0)
   res=[]
   for each in queries:
      typ=each[0]
      day=each[1]
      cap=each[2]
      if day+1 > sumcandy[typ] or (day+1)*cap <= sumcandy[typ-1]:
         res.append(False)
      else:
         res.append(True)
   return res

candiesCount = [7,4,5,3,8]
queries = [[0,2,2],[4,2,4],[2,13,100]]
print(solve(candiesCount, queries))

Đầu vào

[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]

Đầu ra

[True, False, True]