数据结构
网络
关系型数据库管理系统(RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++双城市调度
假设有2N个人。一家公司想组织一次面试。将第i个人送到A城市的费用为costs[i][0]，送到B城市的费用为costs[i][1]。我们必须找到将每个人送到一个城市的最低费用，使得每个城市都有N个人到达。例如，如果给定的列表是[[10, 20], [30, 200], [400, 50], [30, 20]]，输出将是110。因此，我们将把P1送到A城市，费用为10，第二个人送到A城市，费用为30，第三和第四个人送到B城市，费用分别为50和20。
为了解决这个问题，我们将遵循以下步骤：
- n := 数组的大小
- a := n / 2 b := n / 2
- 对数组进行排序，令ans := 0
- for i := 0 to n – 1
- if b = 0 and array[i, 0] <= array[i, 1] and a > 0, then
- a减1
- ans := ans + array[i, 0]
- else
- b减1
- ans := ans + array[i, 1]
- if b = 0 and array[i, 0] <= array[i, 1] and a > 0, then
- return ans
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
return abs(a[0] - a[1]) > abs(b[0] - b[1]);
}
int twoCitySchedCost(vector<vector<int>>& costs) {
int n = costs.size();
int a = n/2;
int 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--;
//cout << a << " " << costs[i][0] << endl;
ans += costs[i][0];
} else {
//cout << costs[i][1] << endl;
b--;
ans += costs[i][1];
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> c = {{10,20},{30,200},{400,50},{30,20}};
cout << ob.twoCitySchedCost(c);
}输入
[[10,20],[30,200],[400,50],[30,20]]
输出
110
更新于：2020年4月28日
415 次浏览
广告