传送门


解题思路

先把所有的数据读下来。

对于地铁,答案直接加,然后把编号放入一个数组a内。

对于公交车,从前往后枚举a数组,然后找到出现最早的且符合价钱大于等于公交车的价钱,然后把这个数删除(变为0)。

然后再考虑有效期是45分钟,为了优化时间,我们可以每一次把数组看做一个队列,当a[first]是0或者时间超过了45分钟时,first++。

这样就保证了数组内的数不超过45个。

最后看一眼时间复杂度,O(NK),K为不超过45。

轻松A掉。

AC代码

 #include<iostream>
#include<cstdio>
using namespace std;
const int maxn=;
int n,x,p[maxn],t[maxn],a[maxn],cnt,fir=;
long long ans;
int main()
{
cin>>n;
for(int i=;i<=n;i++){
scanf("%d%d%d",&x,&p[i],&t[i]);
while(fir<=cnt&&(a[fir]==||t[i]-t[a[fir]]>)) fir++;
ans+=p[i];
if(x==){
a[++cnt]=i;
}else{
for(int j=fir;j<=cnt;j++){
if(a[j]==) continue;
if(p[i]<=p[a[j]]){
a[j]=;
ans-=p[i];
break;
}
}
}
}
cout<<ans<<endl;
return ;
}

//CSP2019普及组 t2

最新文章

  1. linux常用命令-文件搜索命令-locate,which,whereis,grep
  2. espcms特殊标签
  3. javascript 核心语言笔记- 2 语法结构
  4. 一个非常牛比的前端google插件
  5. C++构造函数初始化顺序
  6. StarUML建模软件
  7. struts2 hello world
  8. Linux下/etc/fstab文件详解
  9. Win7如何分享局域网并设置共享文件夹账户和密码
  10. JAVA代码发送邮件示例和解释(二)
  11. 第四周结对项目总结及改进(ui/web)
  12. cept源代码目录结构详解_知识树(转)
  13. HNOI2016做题笔记
  14. Zabbix报警执行远程命令
  15. SQL语句备份和还原数据库
  16. ElasticSearch入门 第五篇:使用C#查询文档
  17. (原创)hibernate 一对多建表实例详解 附上各个注释的含义
  18. ZooKeeper 节点
  19. 天梯赛 L2-023. (模拟) 图着色问题
  20. 【App性能】:TraceView分析法

热门文章

  1. 对浏览器如何计算CSS的研究---------------引用
  2. SQL 使用分区方法
  3. html body标签 语法
  4. 序列式容器————dequeue
  5. [design pattern](8) Command
  6. NBU5240备份系统还原数据库--Linux版
  7. (二)SQL -- 查询
  8. [CSP-S模拟测试]:表达式密码(模拟)
  9. java中的null类型---有关null的9件事
  10. 【C++进阶:atoi()与itoa()】