คำอธิบายปัญหา
กำหนดลิสต์ costs โดย costs[i] = [c1, c2] = ค่าใช้จ่ายส่งคนที่ i ไปเมือง 0 และเมือง 1 ต้องการส่งคนครึ่งหนึ่งไปเมือง 0 อีกครึ่งไปเมือง 1 หาต้นทุนรวมน้อยที่สุด
ตัวอย่าง
costs = [[2,6],[10,3],[4,9],[5,8]] → Output: 17
- คน 0 และ 2 ไปเมือง 0: 2 + 4 = 6
- คน 1 และ 3 ไปเมือง 1: 3 + 8 = 11
- รวม = 17
ขั้นตอนการแก้ปัญหา (Greedy + Sorting)
- สมมติส่งทุกคนไปเมือง 0 ก่อน:
s = sum(x for x,y in costs) - คำนวณ "ความต่าง" หากส่งไปเมือง 1 แทน:
a = [y - x for x,y in costs] - เรียง
aจากน้อยไปมาก (ค่าติดลบ = คุ้มกว่าไปเมือง 1) - เลือกครึ่งแรกของ
a(n/2 คน) บวกเข้ากับs
การตนการทำงาน (Python)
def solve(costs):
s = 0
a = []
for x, y in costs:
s += x
a.append(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)) # Output: 17
อินพุต / เอาต์พุต
Input: [[2, 6], [10, 3], [4, 9], [5, 8]] Output: 17
