下界困难

Question

问题链接 - https://leetcode.com/problems/most-profit-assigning-work/description/

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n=profit.size();
        vector<pair<int,int>> v;
        for(int i=0;i<n;i++){
            v.push_back({-difficulty[i],profit[i]});
        }
        auto comp=[&](pair<int,int> a,pair<int,int> b){
            return a.second>b.second;
        };
        sort(v.begin(),v.end(),comp);
        int ans=0;
        for(auto i:v)cout<<"d-"<<i.first<<" p-"<<i.second<<"||";
        for(int i=0;i<worker.size();i++){
            pair<int,int> p = {-worker[i],0};
            auto lb= lower_bound(v.begin(),v.end(),p);
            ans+=lb!=v.end()?lb->second:0;
        }
        return ans;
    }
};

---

测试用例-

难度=

[5,50,92,21,24,70,17,63,30,53]

利润=

[68,100,3,99,56,43,26,93,55,25]

工人 =

[96,3,55,30,11,58,68,36,26,1]

我不明白为什么上面的 TC 代码返回错误的 ans。当工人的能力为 55 或 58 时，尽管在我的排序向量 v 中 50 位于 5 之前，为什么它会获利 5 而不是 50？

Answer 1

首先，您不满足

std::lower_bound

的要求，即必须对范围进行排序。

您正在对范围进行排序，但您使用

comp

来执行此操作，这仅针对利润进行排序。这导致难度（作为该对的第一个元素）与排序完全无关。

对

std::lower_bound

的调用使用

std::pair

的默认排序，即按第一个元素排序，然后是第二个元素。因为如上所述，第一个元素没有排序，所以

std::lower_bound

的行为是未定义的。

然而，虽然is有接受比较器的

std::lower_bound

的重载，但你不能指望使用它并突然让你的算法工作，因为你的逻辑从根本上是有缺陷的。在目前的形式下，即使您也固定了顺序，您的程序无法发现任何单一难度下可实现的最大利润。这是因为可能还有其他难度较小、利润更高的任务。要找到这些，您仍然需要搜索一些向量（如果已排序）或整个向量（如果未排序）。

---

那么，如何解决这个问题呢？

这就是所谓的“动态规划”技术的用处。您可以操纵数据来对已知的内容进行编码，这样您就不必浪费时间计算冗余答案。关于这个特定问题的一个非常重要的事情是，具有特定技能水平的工人可以在该难度或更低的难度下执行“任何”工作。因此，任何难度下的最大利润始终是该难度或更低难度下所有工作的最大利润。 知道了这一点，您现在可以调整您的利润，使其代表具有特定技能水平的工人在任何工作中可实现的最大利润。您可以按如下方式执行此操作：

// Merge difficulty and profit vectors and order by difficulty
std::vector<std::pair<int, int>> v;
v.reserve(difficulty.size());
for(size_t i = 0; i < difficulty.size(); i++)
{
    v.emplace_back(difficulty[i], profit[i]);
}
std::sort(v.begin(), v.end());

// Calculate maximum profit at each difficulty
for (size_t i = 1; i < v.size(); i++)
{
    v[i].second = std::max(v[i].second, v[i-1].second);
}

现在，您可以依靠

std::lower_bound

找到最近的难度，并且因为您已经计算了最大利润，所以您知道该难度的利润将是该难度之前所有作业的最佳利润。

int ans = 0;
for(int skill : worker)
{
    std::pair<int, int> searchVal{skill, 0};
    auto it = std::lower_bound(v.begin(), v.end(), searchVal);
    if (it != v.end())
    {
        ans += it->second;
    }
}