Kiểm tra xem có thể phục vụ hàng đợi của khách hàng với các ghi chú khác nhau bằng Python hay không

Giả sử chúng ta có một mảng được gọi là ghi chú đại diện cho các ghi chú rupee khác nhau mà khách hàng đang giữ trong một hàng đợi. Tất cả họ đang chờ đợi để mua vé trị giá 50 Rs. Đây là ghi chú có thể có là [50, 100 và 200]. Chúng tôi phải kiểm tra xem chúng tôi có thể bán vé cho mọi người theo thứ tự hay không, ban đầu chúng tôi có 0 Rs trong tay.

Vì vậy, nếu đầu vào giống như các nốt =[50, 50, 100, 100], thì đầu ra sẽ là True cho hai đầu tiên, chúng ta không cần trả về bất cứ điều gì, nhưng bây giờ chúng ta có hai nốt 50 Rs. Vì vậy, đối với hai người cuối cùng, chúng tôi có thể trả lại họ tờ 50 Rs và bán tất cả các vé theo thứ tự.

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

• freq:=một bản đồ trống
• i:=0
• while i
• nếu các ghi chú [i] giống 50, thì
  • freq [50]:=freq [50] + 1
• ngược lại, khi các ghi chú [i] giống 100, thì
  • freq [100]:=freq [100] + 1
  • nếu freq [50] là 0, thì
    • ra khỏi vòng lặp
  • freq [50]:=freq [50] - 1
• nếu không,
  • nếu freq [100]> 0 và freq [50]> 0, thì
    • freq [100]:=freq [100] - 1
    • freq [50]:=freq [50] - 1
  • ngược lại khi freq [50]> =3, thì
    • freq [50]:=freq [50] - 3
  • nếu không,
    • ra khỏi vòng lặp
• i:=i + 1

Ví dụ

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

from collections import defaultdict
def solve(notes):
   freq = defaultdict(int)
   i = 0
   while i < len(notes):
      if notes[i] == 50:
         freq[50] += 1
      elif notes[i] == 100:
         freq[100] += 1
         if freq[50] == 0:
            break
         freq[50] -= 1
      else:
         if freq[100] > 0 and freq[50] > 0:
            freq[100] -= 1
            freq[50] -= 1
         elif freq[50] >= 3:
            freq[50] -= 3
         else:
            break
      i += 1
   if i == len(notes):
      return True
   return False
notes = [50, 50, 100, 100]
print(solve(notes))

Đầu vào

[50, 50, 100, 100]

Đầu ra

True