Lập lịch 2 thành phố (Two City Scheduling) trong C++

Có 2N người. Chi phí bay người i đến thành phố A là costs[i][0], đến B là costs[i][1]. Tìm chi phí nhỏ nhất để bay N người đến mỗi thành phố.

Ví dụ: costs = [[10,20],[30,200],[400,50],[30,20]] -> Output: 110.

Giải pháp: Sắp xếp theo hiệu chi phí tuyệt đối giảm dần. Chọn thành phố rẻ hơn cho người có chênh lệch lớn, đảm bảo mỗi thành phố đúng N người.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;
class Solution {
    static bool cmp(vector<int> a, vector<int> b){
        return abs(a[0] - a[1]) > abs(b[0] - b[1]);
    }
public:
    int twoCitySchedCost(vector<vector<int>>& costs){
        int n = costs.size();
        int a = n/2, b = n/2;
        sort(costs.begin(), costs.end(), cmp);
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(b == 0 || (costs[i][0] <= costs[i][1] && a > 0)){
                a--; ans += costs[i][0];
            } else {
                b--; ans += costs[i][1];
            }
        }
        return ans;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> c = {{10,20},{30,200},{400,50},{30,20}};
    cout << ob.twoCitySchedCost(c);
    return 0;
}

Kết quả

110