[CSP-J 2019]第二题公交换乘 简明题解 by 对面龙哥

简要分析题目

• 题目链接(洛谷)
• 题目链接(AcWing)

普及组的水题，没什么难度，只要处理好优惠票就好了。

存储优惠票

我们先写一个 $ticket$ 类来描述优惠票信息：

class Ticket {                              //Ticket类用于存储优惠票信息
public:
    int time, price;
    Ticket():time(0),price(0){}
    Ticket(int t,int p):time(t),price(p){}
};

然后用 $list$容器按时间顺序存储获得的优惠票( $vector$ 、 $deque$ 当然也可以，但在此题中可能需要大量的中间删除操作，使用 $list$ 效率更高)。并且每当坐公交车时，先用 $check$ 函数检查并删除过期的优惠票，再用 $free$ 函数来判断是否可以使用优惠票。代码如下:

list<Ticket>tic;                            //相比于vector和deque，list容器在中间的插入和删除上效率更高
bool free(int p) {                          //检查是否存在可用的优惠票
    if (tic.empty())return false;
    for(list<Ticket>::iterator iter = tic.begin(); iter != tic.end(); iter++) {
        if (iter->price >= p) {     //可以消耗此优惠票
            tic.erase(iter);    //删除此优惠票
            return true;        //找到符合条件的优惠票，返回true
        }
    }
    return false;                       //上一步中未找到符合条件的优惠票，返回false
}
void check(int t) {                         //检查是否存在已过期的优惠票
    if (tic.empty())return;
    list<Ticket>::iterator iter = tic.begin();
    while (iter->time < t && iter != tic.end()) {
        tic.erase(iter++);
    }
}

模拟过程

之后就是每次坐公交车检查并消耗优惠票(没法用就掏钱)，坐地铁就直接增加总费用并添加优惠票到 $list$ 中。代码如下:

int p;
if (read()) {                               //读取到1，为公交车
    p = read();                         //读取票价
    check(read());                      //第三个读取的数据为乘车时间，检查有无过期优惠票
    if (!free(p)) {                     //如果无法使用优惠票
        ans += p;                   //增加费用
    }
}
else {                                      //不为公交车即为地铁
    p = read();                         //读取票价
    ans += p;                           //增加费用
    tic.push_back(Ticket(read() + 45, p));//获得优惠票，加入list中
}

完整代码

#include <iostream>
#include<cstdio>
#include<list>

using namespace std;

inline int read() {                                             //快读
    int x = 0; char ch = getchar();
    while (ch > '9' || ch < '0')ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch - 48);
        ch = getchar();
    }
    return x;
}

class Ticket {                                                  //Ticket类用于存储优惠票信息
public:
    int time, price;
    Ticket():time(0),price(0){}
    Ticket(int t,int p):time(t),price(p){}
};

list<Ticket>tic;                        //相比于vector和deque，list容器在中间的插入和删除上效率更高
bool free(int p) {                                      //检查是否存在可用的优惠票
    if (tic.empty())return false;
    for(list<Ticket>::iterator iter = tic.begin(); iter != tic.end(); iter++) {
        if (iter->price >= p) {                         //可以消耗此优惠票
            tic.erase(iter);                        //删除此优惠票
            return true;                            //找到符合条件的优惠票，返回true
        }
    }
    return false;                                           //上一步中未找到符合条件的优惠票，返回false
}
void check(int t) {                                             //检查是否存在已过期的优惠票
    if (tic.empty())return;
    list<Ticket>::iterator iter = tic.begin();
    while (iter->time < t && iter != tic.end()) {
        tic.erase(iter++);
    }
}

int n;                                                          //乘车记录数
int ans;                                                        //乘车总费用

int main()
{
    n = read();
    while (n > 0) {
        int p;
        if (read()) {                                   //读取到1，为公交车
            p = read();                             //读取票价
            check(read());                          //第三个读取的数据为乘车时间，检查有无过期优惠票
            if (!free(p)) {                         //如果无法使用优惠票
                ans += p;                       //增加费用
            }
        }
        else {                                          //不为公交车即为地铁
            p = read();                             //读取票价
            ans += p;                               //增加费用
            tic.push_back(Ticket(read() + 45, p));  //获得优惠票，加入list中
        }
        n--;
    }
    printf("%d", ans);
    return 0;
}

总结

题目本身不难，唯一的难点在优惠票的处理上，同时要考虑时间和票价，需要考虑好什么时候需要删除车票。

用 $list$容器效率较高但是不像$vector$ 和 $deque$ 支持随机访问，所以遍历时需要用迭代器，不熟悉的话容易RE。鉴于此题数据规模较小，所以 $vector$ 和 $deque$ 其实也可以，但毕竟用了 $list$ 精(shu)益(ju)求(hao)精(kan)不是吗？

[CSP-J 2019]第二题公交换乘 简明题解 by 对面龙哥

原文：https://www.cnblogs.com/duimianlongge/p/12115463.html