Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/most-profit-assigning-work
: 826. Most Profit Assigning Work
: 你有n份工作與m個工人
: 給定三數列
: difficulty[i]與profit[i]代表第i份工作的收益與困難度
: worker[j]代表工人的能力
: 工人只能接受困難度小於等於自己能力的工作
: 每位工人只能接一份工作 但工作能被重複完成
: 請回傳我們將工作分配給工人後能獲得的最大收益
:
這題用heap或是雙指針都可以
然後我突然想練習看看二分搜
反正都是nlogn
只是二分搜寫起來很麻煩
媽的 早就知道乖乖sort雙指針了
思路:
只要sort工作
然後讓每個員工找到可以做的最大工作就可以了
```cpp
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector
<int>& worker)
{
int res = 0;
int len = difficulty.size();
vector<pair<int,int>> paper;
map<int,int> paper2;
for(int i = 0 ; i < len ; i ++)
{
paper2[difficulty[i]] = max(paper2[difficulty[i]] , profit[i]);
}
for(auto k : paper2)
{
paper.push_back({k.first , k.second});
}
int nmax = 0;
len = paper.size();
for(int i = 0 ; i < len ; i ++)
{
nmax = max(nmax , paper[i].second);
paper[i].second = max(nmax , paper[i].second);
}
int wlen = worker.size();
for(int i = 0 ; i < wlen ; i ++)
{
if(worker[i] < paper[0].first)continue;
if(worker[i] > paper[len-1].first){
res += paper[len-1].second;
continue;
}
int l = 0 ;
int r = len-1;
int m = 0;
while(l < r)
{
int m = (l + r + 1) / 2;
if(paper[m].first <= worker[i])
{
l = m;
}
else
{
r = m - 1;
}
}
res += paper[l].second;
//cout << paper[l].second << " ";
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.19.126 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718684999.A.220.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 378 之 1550 篇)：