LeetCode -- 826. 安排工作以达到最大收益

方法一：二分加枚举

通过二分快速查找小于某个难度值的最大价值。

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        const int n = (int) difficulty.size();
        vector<pair<int, int>> jobs(n);
        for(int i = 0; i < n; i ++ ) {
            jobs[i] = {difficulty[i], profit[i]};
        }

        sort(jobs.begin(), jobs.end());

        int mx = jobs[0].second;
        for(int i = 0; i < n; i ++ ) {
            jobs[i].second = max(mx, jobs[i].second);
            mx = jobs[i].second;
        }

        sort(worker.begin(), worker.end());
        int res = 0, beat = 0;

        for(int i = 0; i < worker.size(); i ++ ) {
            int l = -1, r = n;
            while(l + 1 < r) {
                int mid = l + r >> 1;
                if(jobs[mid].first <= worker[i]) {
                    l = mid;
                } else {
                    r = mid;
                }
            }

            if(l != -1) {
                beat = max(beat, jobs[l].second);
                res += beat;
            }
        }

        return res;
    }
};

方法2：离散化 + 二分 + 树状数组

我们不关心某项工作的种类，我们只关心它的难度值。首先根据难度值进行离散化，再利用树状数组快速查找到低于某项难度的最大价值。

class Solution {

int tr[10010];
int n;

int lowbit(int x) {
    return x & -x;
}

void add(int p, int x) {
    for(int i = p; i <= n; i += lowbit(i)) {
        tr[i] =  max(tr[i], x);
    }
}

int query(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res = max(res, tr[i]);
    }
    return res;
}

public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<int> s(difficulty.begin(), difficulty.end());
　　　　　//离散化
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        n = s.size() + 1;
　　　　 //插入
        for(int i = 0; i < difficulty.size(); i ++ ) {
            int k = lower_bound(s.begin(), s.end(), difficulty[i]) - s.begin() + 1;
            add(k, profit[i]);
        }
　　　　 //找答案
        int res = 0;
        for(auto worke : worker) {
            int k = upper_bound(s.begin(), s.end(), worke) - s.begin(); //upper_bound - 1为小于等于某个数的最大值
            res += query(k);
        }
        return res;
    }
};