資料結構
網路
關係型資料庫管理系統(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 次瀏覽
廣告