Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 2462. Total Cost to Hire K Workers

---

參考資訊：
https://www.cnblogs.com/cnoodle/p/17508179.html
https://www.geeksforgeeks.org/c/c-program-to-implement-priority-queue/

題目：


解答：

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        long long r = 0;
        int i = 0;
        int j = costs.size() - 1;
        priority_queue<int, vector<int>, greater<int>> left;
        priority_queue<int, vector<int>, greater<int>> right;

        while (k-- > 0) {
            while ((left.size() < candidates) && (i <= j)) {
                left.push(costs[i++]);
            }

            while ((right.size() < candidates) && (i <= j)) {
                right.push(costs[j--]);
            }

            int lv = left.size() > 0 ? left.top() : INT_MAX;
            int rv = right.size() > 0 ? right.top() : INT_MAX;

            if (lv <= rv) {
                r += lv;
                left.pop();
            }
            else {
                r += rv;
                right.pop();
            }
        }

        return r;
    }
};