C++での2つの都市のスケジューリング

2N人がいると仮定します。会社は1つの面接を組織したいと考えています。 i人目の人を都市Aに飛ばすための費用は費用[i][0]であり、i人目の人を都市Bに飛ばすための費用は費用[i][1]です。 N人がすべての都市に到着するように、すべての人を都市に飛ばすための最小コストを見つける必要があります。したがって、指定されたリストが[[10、20]、[30、200]、[400、50]、[30、20]]の場合、出力は110になります。したがって、人P1を都市Aにコスト10で送信します。 、都市Aの2人目は30人、3人目は都市Bの4人目、それぞれ50人と20人です。

これを解決するには、次の手順に従います-

• n：=配列のサイズ
• a：=n / 2およびb：=n / 2
• 配列を並べ替えて、ans：=0
• for i：=0からn– 1 −
  • b =0かつarray[i、0] <=array [i、1]かつa> 0の場合、
    • aを1つ減らします
    • ans：=ans + array [i、0]
  • その他
    • bを1つ減らします
    • ans：=ans + array [i、1]
• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

#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