LeetCode-1029 两地调度

📝题目

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

示例：

输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

提示：

· 1 <= costs.length <= 100
· costs.length 为偶数
· 1 <= costs[i][0], costs[i][1] <= 1000

📝思路

这样来看这个问题，公司首先将这 2N 个人全都安排飞往 A 市，再选出 N 个人改变它们的行程，让他们飞往 A 市。因为全部去往 A 市的总费用 $Sum$ 是确定的，改变 N 个人的行程后总费用为 $Sum - \sum_{n=1}^{len/2} (cost[n][0] - cost[n][1])$，自然是每一组A、B费用差值越大越好了😃。

📝题解

int twoCitySchedCost(vector<vector<int>>& costs) {
    int len = costs.size();
    int result = 0;
    vector<int> diff;
    for (int i = 0; i < len; ++i){
        result += costs[i][0];
        diff.push_back(costs[i][0]-costs[i][1]);
    }
    sort(diff.begin(), diff.end());
    for (int i = len-1; i >= len/2; --i){
        result -= diff[i];
    }
    return result;
}