概述
考都考了,那就发一篇吧
(我会把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] 公交换乘所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复