Luobuyu's Blog

0%

2008. 出租车的最大盈利

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.9k 阅读时长 ≈ 2 分钟
使用二分查找，快速找出来前一个。

2008.出租车的最大盈利

题目描述：

你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ，你想要从 1 开到 n ，通过接乘客订单盈利。你只能沿着编号递增的方向前进，不能改变方向。

乘客信息用一个下标从 0 开始的二维数组 rides 表示，其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ，愿意支付 tipi 元的小费。

每一位 你选择接单的乘客 i ，你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。

给你 n 和 rides ，请你返回在最优接单方案下，你能盈利 最多 多少元。

注意：你可以在一个地点放下一位乘客，并在同一个地点接上另一位乘客。

数据范围：

$1\le n \le 10^5, 1\le rides \le 3\times 10^4 $

题解：

使用 $dp[i]$ 表示 $[0,i]$ 个乘客能得到的最大值。对于第 $i$ 个乘客选择接或不接，接的话就需要从 $[0,i-1]$ 找出来上一个 $end_j \le start_i$ 的，如果找不到就只接 $i$ ；不接的话就从 $dp[i-1]$ 转移。

但是需要注意下标问题，如果 $dp[i]$ 表示 $[1,i]$ 的话，那么遍历 $[1,m]$ ，超找第一个小于等于 $rides[i][0]$ 的，可以查找大于 $rides[i][0]$ 的，然后再减一得到 $rides$ 中的下标，但是换算到 $dp$ 下标，需要加 $1$ ，因此相当于不减。而且找不到的时候为 $-1$ ，加 $1$ 后刚好是 $0$ ，可以直接用 $dp[0]$ 。

也可以初始化 $dp[0]$ 为 $rides[0][1] - rides[0][0] + rides[0][2]$ ，使用统一的下标。

lower_bound注意事项：

注意 $upper\_bound$ 传入自定义比较器，类型不同时，cmp(value, element)，查找第一个 cmp为 true的元素。 $lower\_bound$ 是 cmp(element, value)，查找第一个 cmp 为 false 的元素。

传入小于符号时， $upper\_bound$ 查找第一个满足 $value < element$ ，也就是查找大于， $lower\_bound$ 查找第一个 $value \ge element$ ，也就是查找大于等于。

传入小于等于符号时， $upper\_bound$ 查找第一个满足 $value \le element$ ，也就是查找大于等于， $lower\_bound$ 查找第一个 $value \gt element$ ，也就是查找大于。跟二者的含义刚好一反。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    long long maxTaxiEarnings(int n, vector<vector<int>> &rides)
    {
        int m = rides.size();
        sort(rides.begin(), rides.end(), [](const vector<int> &x, const vector<int> &y)
             { return x[1] == y[1] ? x[0] < y[0] : x[1] < y[1]; });
        vector<long long> dp(m + 1);
        for (int i = 1; i <= m; ++i)
        {
            // 查找结束位置小于等于 rides[i][0] 的。
            int index = upper_bound(rides.begin(), rides.begin() + i - 1, rides[i - 1][0], [](int val, const vector<int> &x)
                                    { return val <= x[1]; }) -
                        rides.begin();
                dp[i] = max(dp[i - 1], dp[index] + rides[i - 1][1] - rides[i - 1][0] + rides[i - 1][2]);
        }
        return dp[m];
    }
};