โปรแกรมตรวจว่ากินขนมที่ชอบในวันที่เราชอบได้ไหมใน Python

สมมติว่าเรามีอาร์เรย์ของ calues ​​ที่เป็นบวก candiesCount โดยที่ candiesCount[i] หมายถึงจำนวนแคนดี้ประเภท ith ที่เรามี เรายังมีอาร์เรย์อื่นที่เรียกว่าการสืบค้น โดยที่การสืบค้น[i]มีพารามิเตอร์สามตัว [favoriteType_i, favoriteDay_i, dailyCap_i] เรามีกฎบางอย่าง:

• เริ่มกินขนมกันวันที่ 0.

• เราไม่สามารถกินขนมประเภท i ใด ๆ เว้นแต่ว่าเราได้กินขนมประเภท i-1 ก่อนหน้านี้ทั้งหมด

• เราต้องกินขนมอย่างน้อยวันละหนึ่งลูกจนกว่าจะได้กินหมด

เพื่อรักษากฎเหล่านี้ เราต้องสร้างอาร์เรย์ของค่าบูลีนสำหรับผลลัพธ์การค้นหาแต่ละรายการ และรายการที่ i จะเป็นจริง หากเราสามารถกินลูกอมประเภท FavoriteType_i ในวันที่ชื่นชอบDay_i โดยไม่ต้องกินมากกว่าลูกอม dailyCap_i ในวันใดก็ได้ เราสามารถกินขนมชนิดต่างๆ ได้ในวันเดียวกัน โดยทำตามกฎข้อ 2

ดังนั้น หากอินพุตเป็นเหมือน candiesCount =[7,4,5,3,8], การสืบค้น =[[0,2,2],[4,2,4],[2,13,100]] แล้วผลลัพธ์ จะเป็น [จริง,เท็จ,จริง] เพราะ

• ถ้าเรากินขนมประเภท 0 ในวันที่ 0 และวันที่ 1 เราจะกินขนมประเภท-0 ในวันที่

• เราสามารถกินขนมได้ไม่เกิน 4 เม็ดต่อวัน ถ้าเรากินลูกอม 4 เม็ดทุกวัน เราจะกินลูกอมประเภท 0 ในวันที่ 0 และ 4 ลูกอม 0 แบบ 0 ลูกอมประเภทที่ 1 ในวันที่ 1 แล้ววันที่ 2 เราสามารถกินได้เฉพาะ 4 แบบที่ 1 แบบที่ 2 ลูกอมเราจึงไม่สามารถกินลูกอมประเภท 4 ในวันที่ 2 ได้

• เราสามารถกินขนมได้วันละ 1 ลูก เราจะกินขนมประเภท 2 ในวันที่ 13

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• sumcandy :=รายการที่มีองค์ประกอบเดียว candiesCount[0]

• ดัชนี:=1

• ในขณะที่ดัชนี <ขนาดของ candiesCount ทำ

  • แทรก (sumcandy[index-1] + candiesCount[index]) ที่ส่วนท้ายของ sumcandy

  • ดัชนี :=ดัชนี + 1

• ใส่ 0 ที่ส่วนท้ายของ sumcandy

• res:=รายการใหม่

• สำหรับแต่ละคำถามให้ทำ

  • typ:=แต่ละ[0]

  • วัน:=แต่ละ[1]

  • cap:=อัน[2]

  • ถ้า day+1> sumcandy[typ] หรือ (day+1)*cap <=sumcandy[typ-1] แล้ว

    • ใส่ False ที่ท้าย res

  • มิฉะนั้น

    • ใส่ True ต่อท้าย res

• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

[True, False, True]