leetcode/MostProfitAssigningWork

Most Profit Assigning Work

摸了两个月鱼的胡汉三我又回来了! ( •̀ ω •́ )✧ (其实也不算摸鱼, 只是懒得写笔记了而已)

任务难度, 任务报酬, 工作能力, 求出最大工作利益.

my solutions

worker 可以排个序, 可以节省效率. 问题是 dif(difficulty) 和 pro(profit) 如何处理. 他们是想对于的东西, 直接排序会出错. 而不处理的话效率无法提高. :(

一种直接的方法是 map. 很适用于这种关联型数据结构. 于是乎, 简单实现了一种 map 的解法.

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

        sort(difficulty.begin(), difficulty.end());
        sort(worker.begin(), worker.end());

        int b = 0, e = 0, lbp = 0, sum = 0;
        for (auto abi : worker) {
            while (e < difficulty.size() && abi >= difficulty[e]) {
                ++e;
            }

            for (int i = b; i < e; ++i) {
                lbp = max(prof[difficulty[i]], lbp);
            }

            // printf("%d ", lbp);
            sum += lbp;
            b = e;
        }

        return sum;
    }
};

老夫已经不是以前的老夫了. map 其实也并不高效. 即使是红黑树, 元素的搜索也是有很大消耗的 :(

(那么有没有那么一种优美的数据结构, 其有媲美 vector 的线性迭代, 又去除了 vector 的巨大消耗呢? 有的! 理论上完美的 hash ! 但是要达到完美, 其要解决的首要问题就是碰撞（；´д｀）ゞ但这真的不是一个可以完美解决的问题)

所以, 老夫悟到了一个道理! 复杂的数据结构可以解决复杂的问题, 但其效率远比不上简单的数据结构. 如果一个问题可以用简单的数据结构来解决, 那么这个解法必然很优越. 数据结构的本质是用一种特性去模拟你所需要的特性. 而这种特性实现上的不同带来了数据结构的复杂程度的不同. 比如现在我所需要的 pro 和 dif 的关联性. 所以我用到了 map. (当然你也可以用一个 pair 的 vector 来实现, 其重心又转向了 pair)

那么, 如何用简单的数据结构解决复杂的问题呢? 好问题! 在下也并不是很清楚 (っ °Д °;)っ !. 不过有一些心得. 如果硬要说的话, 是逻辑! 就拿递归和迭代来距离, 递归的实现往往会比迭代简单很多, 而迭代为了追踪元素的改变, 会用到一些较为复杂的数据结构. (但是问题是, 迭代往往比递归更高效, 因为迭代本身的函数调用和元素传递就是一种巨大的消耗〒▽〒) 所以, 对于这个问题, 在下还在摸索中!

好了, 说回来, 最后在下想到的能够不使用额外的复杂数据结构的方法是: 修改 pro 和 fit (颇有点解决不了问题, 解决提问题的人的意思… 或者说好听点, 从源头解决问题?)

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<int> pro { profit[0] };
        vector<int> dif { difficulty[0] };
        size_t size = profit.size();
        for (int i = 1, s = 0; i < size; ++i) {
            int d = difficulty[i];
            int p = profit[i];

            while (s >= 0) {
                if (p > pro[s]) {
                    if (d < dif[s]) {
                        pro.erase(pro.begin() + s);
                        dif.erase(dif.begin() + s);
                        --s;
                    } else {
                        pro.insert(pro.begin() + s + 1, p);
                        dif.insert(dif.begin() + s + 1, d);
                        s = dif.size() - 1;
                        break;
                    }
                } else {
                    if (d < dif[s]) {
                        --s;
                    } else {
                        s = dif.size() - 1;
                        break;
                    }
                }
            }

            if (s == -1) {
                pro.insert(pro.begin(), p);
                dif.insert(dif.begin(), d);
                s = dif.size() - 1;
            }
        }

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

        int b = 0, e = 0, lbp = 0, sum = 0;
        for (auto abi : worker) {
            while (e < dif.size() && abi >= dif[e]) {
                ++e;
            }

            for (int i = b; i < e; ++i) {
                lbp = max(pro[i], lbp);
            }

            sum += lbp;
            b = e;
        }

        return sum;
    }
};

在下虽然对这种量级的代码并不满意, 但是好像暂时想不到什么不用到复杂数据结构, 又能比较高效解决问题的办法了… （；´д｀）ゞ在下还是太菜了…

第二个循环几乎没变, 核心是第一个循环对于数据的处理, 大概是这么一个逻辑:

当前 profit 大于对比元素的 profit
1. 当前 difficulty 小于对比元素的 difficulty
  
  这种情况的话, 对比元素就没有存在的意义了. 删除
2. 当前 difficulty 大于等于对比元素的 difficulty
  
  插入!
当前 profit 小于等于对比元素的 profit
1. 当前 difficulty 小于对比元素的 difficulty
  
  对比元素有存在的价值, 继续便利其他的对比元素
2. 当前 difficulty 大于等于对比元素的 difficulty
  
  当前元素无存在价值, 跳过.

经过这些修改之后, 元素的量会大大减少(其中一个案例好像直接少了一倍以上)

但是, … 这个循环的消耗还是比较大的, 整体的代码量太多了. 这个循环的理解难度也比较大. 所以并不是一个满意的解法…

the best solutions

不贴了, 他是用 pair + sort 解决的. 毫无新意! (虽然的确比较好…)