题目
公司计划面试 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
C++解法
class Solution {
public:
static bool comparator(pair<int, int> & lhs, pair<int, int> & rhs) { return lhs.second > rhs.second; }
int twoCitySchedCost(vector<vector<int>>& costs) {
vector<pair<int, int>> deltas;
for (int i = 0; i < costs.size(); i++) {
auto item = costs[i];
deltas.push_back(pair<int,int>(i, abs(item[0] - item[1])));
}
sort(deltas.begin(), deltas.end(), comparator);
int ACount = 0;
int BCount = 0;
int cost = 0;
int N = (int)costs.size() / 2;
for (int i = 0; i < deltas.size(); i++) {
auto item = costs[deltas[i].first];
if (ACount == N || BCount == N) {
if (ACount == N) {
cost += item[1];
} else {
cost += item[0];
}
} else {
if (item[0] < item[1]) {
cost += item[0];
ACount++;
} else {
cost += item[1];
BCount++;
}
}
}
return cost;
}
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-city-scheduling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
