洛谷 P5661 公交换乘 & [NOIP2019普及组] (模拟)
2024-10-07 09:39:56
传送门
解题思路
先把所有的数据读下来。
对于地铁,答案直接加,然后把编号放入一个数组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
最新文章
- linux常用命令-文件搜索命令-locate,which,whereis,grep
- espcms特殊标签
- javascript 核心语言笔记- 2 语法结构
- 一个非常牛比的前端google插件
- C++构造函数初始化顺序
- StarUML建模软件
- struts2 hello world
- Linux下/etc/fstab文件详解
- Win7如何分享局域网并设置共享文件夹账户和密码
- JAVA代码发送邮件示例和解释(二)
- 第四周结对项目总结及改进(ui/web)
- cept源代码目录结构详解_知识树(转)
- HNOI2016做题笔记
- Zabbix报警执行远程命令
- SQL语句备份和还原数据库
- ElasticSearch入门 第五篇:使用C#查询文档
- (原创)hibernate 一对多建表实例详解 附上各个注释的含义
- ZooKeeper 节点
- 天梯赛 L2-023. (模拟) 图着色问题
- 【App性能】:TraceView分析法