复赛二：公交换乘(transfer)

洛谷：P5661
OJ：P4963

解题思路：

我们需要模拟小轩的乘车过程，按照时间顺序处理每一条乘车记录，并根据优惠方案计算总花费。关键在于如何管理和使用地铁乘坐后获得的优惠票，以及如何在乘坐公交车时正确地应用这些优惠票。

算法步骤：

  1. 数据结构设计：
    • 使用一个队列（deque）来存储优惠票，每张优惠票包含两个信息：地铁乘车开始时间（t_subway）和地铁票价（price_subway）。
    • 队列中的优惠票按照获得的顺序排列，新的优惠票添加到队尾，使用优惠票时从队首开始检查。
  2. 按时间顺序处理乘车记录：对于每一条乘车记录，按照以下步骤处理：
    • 如果是地铁乘坐（type == 0）：
      • 将地铁票价加到总花费中（totalCost += price）。
      • 根据地铁乘坐获得一张优惠票，记录其开始时间和票价，添加到优惠票队列的尾部。
    • 如果是公交车乘坐（type == 1）：
      • 移除过期的优惠票：
        • 检查优惠票队列的队首，如果当前公交车乘车开始时间与优惠票的地铁乘车开始时间之差大于45分钟，则该优惠票已过期，从队首移除。
        • 重复上述步骤，直到队首的优惠票未过期或队列为空。
      • 查找可用的优惠票：
        • 从优惠票队列的队首开始，遍历所有未过期的优惠票。
        • 对于每一张优惠票，检查以下条件：
          • 公交车票价是否小于等于优惠票的地铁票价（price <= it->price）。
          • 当前公交车乘车开始时间与优惠票的地铁乘车开始时间之差是否小于等于45分钟（time - it->time <= 45）。
        • 如果找到满足条件的优惠票，立即使用该优惠票：
          • 从优惠票队列中移除这张优惠票（discountTickets.erase(it)）。
          • 不需要将公交车票价加到总花费中。
          • 跳出循环，结束对优惠票的遍历。
      • 如果没有可用的优惠票：
        • 将公交车票价加到总花费中（totalCost += price）。

详细解释：

  • 定义数据结构：
    • 使用结构体 Ticket 来表示优惠票，包含地铁乘车开始时间 time 和地铁票价 price。
    • 使用 deque<Ticket> discountTickets 来存储所有未使用且未过期的优惠票。
  • 处理地铁乘坐：
    • 将地铁票价累加到总花费 totalCost 中。
    • 创建一张新的优惠票，记录地铁乘车的开始时间和票价，添加到 discountTickets 队列的尾部。
  • 处理公交车乘坐：
    • 移除过期的优惠票：
      • 使用 while 循环，从队列的前端开始，检查优惠票是否已过期（time - discountTickets.front().time > 45）。
      • 如果优惠票已过期，使用 pop_front() 将其从队列中移除。
      • 重复上述步骤，直到队列为空或队首的优惠票未过期。
    • 查找可用的优惠票：
      • 使用 for 循环，从队列的前端开始遍历所有未过期的优惠票。
      • 对于每张优惠票，检查：
        • 公交车票价是否小于等于该优惠票的地铁票价（price <= it->price）。
        • 优惠票是否在有效期内（time - it->time <= 45）。
      • 如果找到符合条件的优惠票：
        • 使用 erase(it) 将其从队列中移除。
        • 标记 usedTicket = true，表示已使用优惠票。
        • 使用 break 跳出循环，避免继续遍历后续的优惠票。
    • 更新总花费：
      • 如果使用了优惠票（usedTicket == true），则不需要将公交车票价加到 totalCost 中。
      • 如果没有可用的优惠票，需要将公交车票价累加到 totalCost 中。

算法复杂度分析：

  • 时间复杂度：
    • 对于每次乘车记录，地铁乘坐的处理是 $O(1)$ 的。
    • 对于公交车乘坐，最坏情况下需要遍历队列中的所有优惠票。但由于优惠票的有效期为45分钟，且乘车记录不会在同一分钟内出现，队列中的优惠票数量不会太多，最多为45张。因此，总的时间复杂度近似为 $O(n)$。
  • 空间复杂度：
    • 需要一个队列来存储未使用且未过期的优惠票，最多存储 $O(n)$ 张优惠票（但实际不会达到这个数量，因为优惠票会过期）。

注意事项：

  • 优惠票的使用规则：
    • 必须使用满足条件的最早获得的优惠票。
    • 优惠票必须在有效期内（45分钟内）。
    • 公交车票价必须小于等于优惠票关联的地铁票价。
  • 优惠票的管理：
    • 及时移除过期的优惠票，避免遍历无效的票。
    • 在查找可用的优惠票时，从队列的前端开始，确保使用的是最早获得的优惠票。

代码实现：

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**************************************************************** 
 * Description: 2019年普及组第二题   公交换乘
 * Author: Alex Li
 * Date: 2024-09-24 14:56:22
 * LastEditTime: 2024-09-24 18:19:29
****************************************************************/
#include <iostream>
#include <deque>

using namespace std;

struct Ticket {
    int time;   // 地铁乘车开始时间 t_subway
    int price;  // 地铁票价 price_subway
};

int main() {
    int n;
    cin >> n;
    deque<Ticket> discountTickets;  // 存储优惠票
    int totalCost = 0;  // 总花费

    for (int i = 0; i < n; ++i) {
        int type, price, time;
        cin >> type >> price >> time;
        if (type == 0) {
            // 地铁乘坐
            totalCost += price;
            discountTickets.push_back({time, price});
        } else {
            // 公交车乘坐
            // 移除过期的优惠票
            while (!discountTickets.empty() && time - discountTickets.front().time > 45) {
                discountTickets.pop_front();
            }
            // 查找可用的优惠票
            bool usedTicket = false;
            for (auto it = discountTickets.begin(); it != discountTickets.end(); ++it) {
                if (price <= it->price && time - it->time <= 45) {
                    // 使用这张优惠票
                    discountTickets.erase(it);
                    usedTicket = true;
                    break;
                }
            }
            if (!usedTicket) {
                // 支付公交车票价
                totalCost += price;
            }
        }
    }

    cout << totalCost << endl;
    return 0;
}
Previous Topic
Back to Lesson
Next Topic