C ++中的两个城市调度
假设有2N个人。一家公司希望组织一次面试。第i个人飞往城市A的成本是成本[i][0],第i个人飞往城市B的成本是成本[i][1]。我们必须找到让每个人飞往一个城市的最低成本,这样N人才能到达每个城市。因此,如果给定的列表是[[10,20],[30,200],[400,50],[30,20]],则输出将为110。因此,我们将以成本10将人P1发送到城市A,第二人到城市A的费用为30,第三人和第四人到城市B的费用分别为50和20。
为了解决这个问题,我们将遵循以下步骤-
n:=数组的大小
a:=n/2和b:=n/2
对数组进行排序,然后让ans:=0
对于i:=0至n–1−
将b减1
ans:=ans+array[i,1]
减少1
ans:=ans+array[i,0]
如果b=0且array[i,0]<=array[i,1]且a>0,则
其他
返回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