f函数的空间复杂度是
O
(
M
)
O(M)
O(M)，因为i和j都只前进不回退，也就是只遍历2次m长度的数组N为任务数组与工人数组的较大值
然后主函数排序两个数组是
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)，二分加上f函数最多也不超过
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)
所以时间复杂度
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)
空间复杂度低于
O
(
N
)
O(N)
O(N)，队列长度取决于完成任务的数量
int deque[50001]; // 一个双端队列，用于存储可能通过使用或不使用药丸完成的任务。
// 辅助函数，用于判断是否能在当前条件下完成m个任务。
bool f(vector<int>& ts, vector<int>& ws, int p, int s, int m) {
int h = 0, t = 0; // 双端队列的头部和尾部指针
//i指向最容易完成的第一个任务，j指向能力第m强的工人
//遍历m个最容易完成的任务以及能力最强的m个工人
for (int i = 0, j = ws.size() - m; j < ws.size(); ++j) {
// 遍历每一个工人，并尝试分配任务
while (i < m && ts[i] <= ws[j]) {
// 如果当前任务可以由工人直接完成，则将其加入队列
deque[t++] = ts[i++];
}
//经过上面的if如果队列里面没东西，说明该试试药了
//如果队列里面有东西，可能是前一个工人嗑药留下的
if (h == t || ws[j] < deque[h]) {
// 如果队列为空，或当前工人无法完成队列头部的任务，则尝试使用药丸
--p; // 使用一颗药丸
while (i < m && ts[i] <= ws[j] + s) {
// 将可以通过使用药丸完成的任务加入队列
deque[t++] = ts[i++];
}
if (h == t || p < 0 || ws[j] + s < deque[h]) {
// 如果队列依然为空，或药丸用完，或即使使用药丸也无法完成队列头部的任务，则返回false
return false;
}
--t; // 上面没返回说明嗑药有用，完成最难的任务，一点子贪心各位肯定能懂，队列尾部指针前移
} else {//否则
++h; // 工人直接完成了队列头部的任务，队列头部指针后移
}
}
//能走到这就说明能完成
return true;