C++의 Two City Scheduling

<시간/>

2N명이 있다고 가정합니다. 회사에서 하나의 인터뷰를 조직하려고 합니다. i번째 사람을 도시 A로 보내는 데 드는 비용은 비용[i][0]이고 i번째 사람을 도시 B로 보내는 데 드는 비용은 비용[i][1]입니다. N명이 모든 도시에 도착할 수 있도록 모든 사람을 도시로 보내는 데 드는 최소 비용을 찾아야 합니다. 따라서 주어진 목록이 [[10, 20], [30, 200], [400, 50], [30, 20]]이면 출력은 110이 됩니다. 따라서 사람 P1을 비용 10으로 도시 A로 보냅니다. , 두 번째 사람은 비용 30으로 도시 A에, 세 번째 및 네 번째 사람은 도시 B에 비용 50 및 20으로 각각 이동합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=배열의 크기
a :=n / 2 및 b :=n / 2
배열을 정렬하고 ans :=0으로 둡니다.
i에 대해 :=0 ~ n – 1 −
- b =0이고 array[i, 0] <=array[i, 1]이고 a> 0이면
  - 1씩 감소
  - ans :=ans + 배열[i, 0]
- 기타
  - b를 1 감소
  - ans :=ans + 배열[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]]