Chương trình Python tìm chi phí tối thiểu gửi người vào 2 thành phố

Cho danh sách costs với costs[i] = [c1, c2] chi phí người i đến thành phố 0 và 1. Cần gửi bằng số lượng người vào 2 thành phố, tìm chi phí tối thiểu.

Ví dụ

costs = [[2,6],[10,3],[4,9],[5,8]]
Output: 17
Giải thích: Người 0,2 -> thành phố 0 (2+4=6). Người 1,3 -> thành phố 1 (3+8=11). Tổng=17.

Thuật toán (Greedy + Sorting)

1. Giả định ban đầu gửi tất cả về thành phố 0, tổng chi phí s = sum(c1).
2. Tính chênh lệch diff = c2 - c1 cho mỗi người (chi phí thêm nếu chuyển sang thành phố 1).
3. Sắp xếp diff tăng dần.
4. Chọn n/2 người có diff nhỏ nhất (tiết kiệm nhất) chuyển sang thành phố 1.
5. Kết quả: s + sum(n/2 diff nhỏ nhất).

Code Python

def solve(costs):
    s = 0
    a = []
    for x, y in costs:
        s += x           # giả định tất cả đi thành phố 0
        a.append(y - x)  # chênh lệch nếu chuyển sang thành phố 1
    
    a.sort()             # sắp xếp chênh lệch tăng dần
    for i in range(len(a) // 2):
        s += a[i]        # thêm chênh lệch của n/2 người tiết kiệm nhất
    return s

# Test
costs = [[2,6],[10,3],[4,9],[5,8]]
print(solve(costs))  # 17

Giải thích chi tiết

costs:     [2,6]  [10,3]  [4,9]  [5,8]
c1 (city0):  2     10      4      5   -> sum = 21
diff=c2-c1:  4     -7      5      3
sorted diff: -7, 3, 4, 5
n/2 = 2 người đầu: -7 + 3 = -4
Total = 21 + (-4) = 17

Tại sao đúng?

Chuyển người i từ city 0 → city 1 thay đổi chi phí diff_i = c2_i - c1_i. Muốn minimize tổng, chọn n/2 người có diff nhỏ nhất (có thể âm = tiết kiệm).

Độ phức tạp

• Thời gian: O(n log n) do sort.
• Không gian: O(n) cho mảng diff.

Biến thể

Nếu không cần bằng số lượng: chọn min(c1, c2) cho mỗi người.