สมมติว่ามีร้านขายขนมที่มีขนมชนิดต่างๆ N แบบให้เลือก และให้ราคาของขนมชนิดต่างๆ ทั้งหมด N ชนิด ทางร้านยังมีข้อเสนอที่น่าสนใจ ตามข้อเสนอนี้ เราสามารถซื้อขนมลูกเดียวจากร้านค้าและรับขนมชนิดอื่น ๆ ได้สูงสุด K ชนิดฟรี เราต้องหาจำนวนเงินขั้นต่ำที่เราต้องใช้เพื่อซื้อลูกอม N ชนิดต่างๆ ทั้งหมด นอกจากนี้เรายังต้องหาจำนวนเงินสูงสุดที่เราต้องใช้เพื่อซื้อลูกอม N ชนิดต่างๆ ทั้งหมด จากทั้งสองกรณี เราต้องใช้ข้อเสนอและรับแคนดี้คืนให้ได้มากที่สุด หากมีลูกอม k หรือมากกว่า เราต้องเลือก k candies สำหรับการซื้อลูกอมทุกครั้ง แต่ถ้ามีลูกอมน้อยกว่า k เม็ด เราต้องเลือกลูกอมทั้งหมดเพื่อซื้อลูกอม
ดังนั้น หากอินพุตเท่ากับราคา =[4, 3, 2, 5] และ k =2 ผลลัพธ์จะเป็นค่าต่ำสุด =5 และสูงสุด =9 เนื่องจากเมื่อ k เป็น 2 หากเราซื้อลูกอมหนึ่งลูกและ เราสามารถรับเพิ่มอีกสองคนได้ฟรี ในกรณีแรกเราสามารถซื้อลูกอมราคา 2 และนำลูกอมราคา 4 และ 5 ไปฟรี นอกจากนี้เรายังสามารถซื้อลูกอมมูลค่า 3 ได้อีกด้วย ดังนั้นต้นทุนขั้นต่ำ =2 + 3 =5 ในทางกลับกัน ในวินาที กรณีเราซื้อลูกอมราคา 5 และรับลูกอมราคา 2 และ 3 ฟรี หรือซื้อลูกอมมูลค่า 4 ได้เช่นกัน ดังนั้น ต้นทุนสูงสุด =4 + 5 =9
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน get_min() นี่จะใช้เวลา A,k
-
n :=ขนาดของ A
-
เรียงลำดับรายการ A
-
res :=0, i:=0
-
ในขณะที่ n ไม่ใช่ศูนย์ ให้ทำ
-
res :=res + A[i]
-
น :=น-k
-
ผม :=ผม + 1
-
-
ผลตอบแทน
-
กำหนดฟังก์ชัน get_max() นี่จะใช้เวลา A, k
-
n :=ขนาดของ A
-
เรียงลำดับรายการ A
-
res :=0, idx :=0
-
ผม:=n-1
-
ในขณะที่ i>=idx ทำ
-
res :=res + A[i]
-
idx :=idx + k
-
ผม :=ผม - 1
-
-
ผลตอบแทน
-
จากวิธีหลัก ให้เรียกฟังก์ชันทั้งสองนี้เพื่อรับผลลัพธ์
-
get_min(A, k)
-
get_max(A, k)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def get_min(A,k): n = len(A) A.sort() res = 0 i=0 while(n): res += A[i] n = n-k i += 1 return res def get_max(A, k): n = len(A) A.sort() res = 0 idx = 0 i=n-1 while(i>=idx): res += A[i] idx += k i -= 1 return res A = [4, 3, 2, 5] k = 2 print(get_min(A, k),get_max(A, k))
อินพุต
[4, 3, 2, 5], 2
ผลลัพธ์
5 9
