我是靠谱客的博主 高大羽毛,最近开发中收集的这篇文章主要介绍P5661 [CSP-J2019] 公交换乘,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

考都考了,那就发一篇吧

(我会把pj前三题的题解做个整合版发在lg博客里,敬请期待!)

这道题基本在意料之中,和龙虎斗类型相似的枚举模拟题,虽然算法简单但是小坑无数

Part 1

看到这题第一反应是“这么简单的一题啊”

迅速开编。

直接模拟即可。开变量记录上一张票的截止时间,逢公交判断即可。

发现可以边读入边处理,节省空间

5min after...

诶肿么样例输错了?![蒟蒻在线懵逼]

好再来康康...

诶!

由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效,而本次公交车的票价为 6 元,高于第五条记录中地铁的票价 5 元,所以不能使用优惠票

woc...还有这个要求!

Part 2

那好办,直接再开个变量记录上一次地铁票价,加一个判断就成。

3min后...

好,我们来看看第一个样例...啊!输对了![蒟蒻的笑容]

然后突然扫到一句话:

如果有多张优惠票满足条件,则优先消耗获得最早的优惠票。

woc!!还会有多张优惠票?!那...直接开一个变量记录的方法直接推翻。

[来自蒟蒻的尴尬而又不是礼貌的微笑]

Part 3

于是决定开结构体数组存储票价信息。

然后又发现如果每次做公交时都从头遍历一遍所有票会T,所以又愣住了

然后突然想起 P2058 [NOIp2016] 海港的一种“滑动窗口”算法,惊讶的发现可以用于这道题。

于是算法就是记录下每次可用票的区间[x,y]的x和y,于是循环可以从x至y,就不会T了。

可用票的区间定义为:全体“未过期”的票包含在此区间内。

有那么一瞬间想到了(在一位奆佬博客里看到过的)优先队列,但是忘了肿么写了。所以就采用了结构体数组加“滑动窗口”。蒟蒻太弱了居然没有意识到这就是优先队列

于是代码就有了。15:30过了大样例,就默认锕了。

#include <iostream>

using namespace std;
const int MAXN = 100005;
struct Ticket {
    int price, time, used;
} q[MAXN];
int head, tail, n, cost;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int op, price, time;
        cin >> op >> price >> time;
        if (op == 0) {
            cost += price;
            q[tail].time = time + 45;
            q[tail++].price = price;
        } else {
            while (head < tail && q[head].time < time) {
                head++;
            }
            bool found = false;
            for (int j = head; j < tail; ++j) {
           
                if (q[j].price >= price && q[j].used == 0) {
             
                    found = true;
                    q[j].used = 1;
                    break;
                }
            }
      
            if (!found) cost += price;
        }
    }
    cout << cost << endl;
    return 0;
}

最后

以上就是高大羽毛为你收集整理的P5661 [CSP-J2019] 公交换乘的全部内容,希望文章能够帮你解决P5661 [CSP-J2019] 公交换乘所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(63)

评论列表共有 0 条评论

立即
投稿
返回
顶部