สมมติว่าเรามีรายการที่เรียกว่าค่าใช้จ่าย โดยที่ค่าใช้จ่าย[i] มี [c1, c2] ระบุว่าสำหรับบุคคลที่ i มีค่าใช้จ่าย c1 จำนวนในการไปถึงเมือง 0 และมีค่าใช้จ่าย c2 จำนวนในการไปถึงเมือง 1 เราต้องการให้ผู้คนจำนวนเท่ากันไปที่เมือง 0 เป็นเมือง 1 เรา ต้องหาต้นทุนขั้นต่ำที่ต้องการ
ดังนั้น ถ้า input เท่ากับ cost =[[2, 6],[10, 3],[4, 9],[5, 8]] ผลลัพธ์จะเป็น 17 เพราะคนที่ 0 และ 2 จะไปที่ เมือง 0 และบุคคลที่ 1 และ 3 ไปยังเมือง 1 ดังนั้นสำหรับเมือง 0 ค่าใช้จ่ายคือ 2+4 =6 และสำหรับเมือง 1 ค่าใช้จ่ายคือ 8+3 =11 รวมเป็น 17
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- s :=0
- a :=รายการใหม่
- สำหรับแต่ละคู่ (x, y) ในต้นทุน ทำ
- s :=s + x
- ใส่ (y - x) ลงใน a ต่อท้าย
- เรียงลำดับรายการ
- สำหรับฉันในช่วง 0 ถึงพื้นของ (ขนาดของ a / 2) - 1 ทำ
- s :=s + a[i]
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(costs): s = 0 a = [] for x, y in costs: s += x a += (y - x,) a.sort() for i in range(len(a) // 2): s += a[i] return s costs = [[2, 6],[10, 3],[4, 9],[5, 8]] print(solve(costs))
อินพุต
[[2, 6],[10, 3],[4, 9],[5, 8]]
ผลลัพธ์
17
