Two City Scheduling ใน C++

สมมติมีคน 2N คน บริษัทต้องการจัดสัมภาษณ์หนึ่งครั้ง ค่าใช้จ่ายในการบินคนที่ i ไปเมือง A คือ costs[i][0] และค่าใช้จ่ายบินไปเมือง B คือ costs[i][1] เราต้องหาค่าใช้จ่ายต่ำสุดในการบินทุกคนไปเมือง ใดเมืองหนึ่ง โดยที่ N คนต้องไปเมือง A และ N คนไปเมือง B

เช่น ถ้า given list คือ [[10, 20], [30, 200], [400, 50], [30, 20]] ผลลัพธ์จะเป็น 110 เราจะส่งคน P1 ไปเมือง A ค่าใช้จ่าย 10 คนที่สองไปเมือง A ค่าใช้จ่าย 30 คนที่สามและสี่ไปเมือง B ค่าใช้จ่าย 50 และ 20 ตามลำดับ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• n := ขนาดของ array
• a := n / 2 และ b := n / 2
• Sort array และให้ 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]
• return 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--;
                ans += costs[i][0];
            } else {
                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);
}

Input

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

Output

110