Pythonでさまざまなメモを使用して顧客キューを提供できるかどうかを確認します

顧客がキューに保持しているさまざまなルピーノートを表すnotesという配列があるとします。彼らは皆、50ルピー相当のチケットを購入するのを待っています。ここで可能なメモは[50、100、200]です。チケットを順番に販売できるかどうかを確認する必要があります。最初はRs0を手にしています。

したがって、入力がnotes =[50、50、100、100]の場合、最初の2つは出力がTrueになりますが、何も返す必要はありませんが、Rs50のノートが2つあります。したがって、最後の2つについては、50ルピーのノートを返却し、すべてのチケットを順番に販売できます。

これを解決するには、次の手順に従います-

• freq：=空のマップ
• i：=0
• <ノートのサイズである間、
  • notes [i]が50と同じ場合、
    • freq [50]：=freq [50] + 1
  • それ以外の場合、notes [i]が100と同じ場合、
    • freq [100]：=freq [100] + 1
    • freq [50]が0の場合、
      • ループから抜け出す
    • freq [50]：=freq [50]-1
  • それ以外の場合、
    • freq[100]>0かつfreq[50]>0の場合、
      • freq [100]：=freq [100]-1
      • freq [50]：=freq [50]-1
    • それ以外の場合、freq [50]> =3の場合、
      • freq [50]：=freq [50]-3
    • それ以外の場合、
      • ループから抜け出す
  • i：=i + 1
• iがノートのサイズと同じ場合、
  • Trueを返す
• Falseを返す

例

理解を深めるために、次の実装を見てみましょう-

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

入力

[50, 50, 100, 100]

出力

True