การจัดตารางเวลาสองเมืองใน C++

สมมติว่ามี 2N คน บริษัทต้องการจัดให้มีการสัมภาษณ์หนึ่งครั้ง ค่าใช้จ่ายในการบินบุคคลที่ i ไปยังเมือง A คือค่าใช้จ่าย[i][0] และค่าใช้จ่ายในการบินบุคคลที่ i ไปยังเมือง B คือค่าใช้จ่าย[i][1] เราต้องหาต้นทุนขั้นต่ำในการบินทุกคนไปยังเมืองหนึ่งเพื่อให้คน N คนมาถึงทุกเมือง ดังนั้นหากรายการที่กำหนดคือ [[10, 20], [30, 200], [400, 50], [30, 20]] ผลลัพธ์จะเป็น 110 ดังนั้นเราจะส่งบุคคล P1 ไปยังเมือง A ด้วยราคา 10 , คนที่สองไปยังเมือง A ด้วยราคา 30, คนที่สามและสี่ไปยังเมือง 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 + 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