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