โปรแกรมหาจำนวนเหรียญสูงสุดที่เราสามารถรับได้โดยใช้ Python

สมมติว่ามีกองเหรียญจำนวน 3*n และมีขนาดต่างกัน ผู้เล่นสามคนกำลังเล่นเกมดังนี้ -

• ในแต่ละขั้นตอน ผู้เล่น 1 จะเลือกเหรียญใดก็ได้ 3 กอง

• ทางเลือกของเขา Player2 จะเลือกกองที่มีจำนวนเหรียญสูงสุด

• ผู้เล่น 1 จะเลือกกองถัดไปด้วยจำนวนเหรียญสูงสุด

• Player3 จะเลือกกองสุดท้าย

• ทำซ้ำขั้นตอนเหล่านี้จนกว่าจะไม่มีกองเหรียญอีกต่อไป

ตอนนี้ถ้าเรามีอาร์เรย์ของจำนวนเต็มที่เรียกว่า piles โดยที่ piles[i] คือจำนวนเหรียญในกอง ith เราก็ต้องหาจำนวนเหรียญสูงสุดที่ผู้เล่น 1 สามารถมีได้

ดังนั้น ถ้าอินพุตเหมือน piles =[2,4,1,2,7,8] ผลลัพธ์จะเป็น 9 เพราะในตอนแรกเราสามารถเลือก triplet (2,7,8) แล้ว Player2 จะเลือก 8 Player1 เลือก 7 และ 2 สำหรับ Player3 จากนั้นเลือกแฝดอีกครั้ง (1,2,4) จากนั้น Player2 เลือกกองที่มีเหรียญ 4 จากนั้น Player1 เลือก 2 และเหลือ 1 สำหรับ Player3 ปัจจุบัน Player1 มี 7+2 =9 เหรียญ ซึ่งเป็นจำนวนสูงสุด

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

• เรียงลำดับรายการกอง

• ตอบ :=0

• ในขณะที่ขนาดของกองไม่เท่ากับ 0 ทำ

  • ans :=ans + องค์ประกอบสุดท้ายที่สองจากกอง

  • ลบองค์ประกอบสุดท้ายที่สองออกจากกอง

  • ลบองค์ประกอบสุดท้ายออกจากกอง

  • ลบองค์ประกอบแรกออกจากกอง

• กลับมาอีกครั้ง

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

ตัวอย่าง

def solve(piles):
   piles.sort()
   ans = 0
   while(len(piles)!=0):
      ans = ans + piles[-2]
      del piles[-2]
      del piles[-1]
      del piles[0]
   return ans
piles = [2,4,1,2,7,8]
print(solve(piles))

อินพุต

[2,4,1,2,7,8]

ผลลัพธ์

9