Lập lịch hai thành phố trong C ++

Giả sử có 2 người. Một công ty muốn tổ chức một cuộc phỏng vấn. Chi phí bay người thứ i đến thành phố A là chi phí [i] [0] và chi phí bay người thứ i đến thành phố B là chi phí [i] [1]. Chúng ta phải tìm chi phí tối thiểu để bay mỗi người đến một thành phố, sao cho N người đến mỗi thành phố. Vì vậy, nếu danh sách đã cho là [[10, 20], [30, 200], [400, 50], [30, 20]] thì kết quả sẽ là 110. Vì vậy, chúng tôi sẽ cử người P1 đến thành phố A với chi phí 10 , Người thứ hai đến thành phố A với chi phí 30, người thứ ba và thứ tư đến thành phố B với chi phí lần lượt là 50 và 20.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng
• a:=n / 2 và b:=n / 2
• Sắp xếp mảng và đặt ans:=0
• for i:=0 to n - 1 -
  • nếu b =0 và mảng [i, 0] <=mảng [i, 1] và a> 0, thì
    • giảm a đi 1
    • ans:=ans + array [i, 0]
  • khác
    • giảm b đi 1
    • ans:=ans + array [i, 1]
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[[10,20],[30,200],[400,50],[30,20]]

Đầu ra

110