Problem C Emergency Evacuation 一道思维题
2024-09-06 14:08:59
题目描述
输入
输出
样例
样例输入
样例输入一
样例输入二
样例输出
样例输出一
9
样例输出二
1008
一句话题意:给你一个车厢和一些人,这些人都坐在座位上,求这些人全部出去的时间最小值。
分析
我们先拿最简单的情况来说:车厢中只有一个人,比如下面这幅图
那么很显然,他到达出口所需要的花费步数为5+1=6
是不是太简单了,那我们再加一个人
那么新加的这个人到出口所需要的步数为2+2=4
因为6大于4,所以在第一个人到达距离出口的步数为2的地方时,第二个人已经从出口离开车厢,不会对结果造成影响
最终答案仍为6
那么我们再加一个人
第三个人到达出口所需要的时间为1+1=2
因为2、4、6都不相等,所以此时最终答案仍然为6
这时,我们要加一个最为关键的人——四号
我们会发现4号到达出口的时间和1号一样都为6
这时,问题就来了,1号和4号显然不能同时走出车厢,而他们走出车厢的最小步数又都为6
所以,1号和4号必定有一个人需要停留一步,在下一步时再排到另一个人的后面
这时,因为有了停留的这一步,最大步数就变成了6+1=7
我们再加一个人,把最后一种情况考虑到
5号到达门口需要的最少步数为2+5=7,那么他能不能在第七步时走出车厢呢
答案是不能的,因为前面的1号和4号都需要走六步才能到达出口
1号和4号中必定有一个人会花费7步,这时会与5号的7步相冲突
所以5号又要推迟一步,变成8步
同样的我们再加一个人
6号需要的步数也为7,所以5号又要推迟一步,变为9步
最后我们再把剩余的一个人加上
他的步数为5步,所以不会对结果产生影响
所以样例一的最终答案为9步
代码
知道了思路,下一步就是代码实现了
我们要先处理出每一个人到达出口的最小步数,然后排一下序
最后我们由大到小遍历,如果遇到相同的就把步数往后推一个
需要注意的是,数组要开500*500*2,不要开小了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;//数组不要开小了
int r,s,p;
int jl[maxn];
int solve(int bb){
if(bb<=s) return s-bb+;
else return bb-s;
}
int main(){
scanf("%d%d%d",&r,&s,&p);
for(int i=;i<=p;i++){
int aa,bb;
scanf("%d%d",&aa,&bb);
jl[i]=r-aa++solve(bb);//求出每个节点到出口的最小步数
}
sort(jl+,jl++p);//排序
int ans=-,cnt=;
for(int i=;i<=p;i++){
if(jl[i]==cnt || ans>=jl[i]) ans++;
//如果出现相同的或者是当前的最大步数大于等于该节点的步数,步数往后推移一步
//这里的当前的最大步数大于等于该节点的步数说明之前一定遍历到了比jl[i]更小的节点
//而且该节点被遍历了两次及以上,这时我们也需要把ans++
else ans=max(ans,jl[i]);//不相同取较大值
cnt=jl[i];//记录上一个元素
}
printf("%d\n",ans);
return ;
}
最新文章
- win10_x64更新错误解决: 安装一些更新时出现问题,但我们稍后会重试。如果持续出现这些问题,并且你想要搜索Web或联系支持人员以获取相关信息,以下信息可能会对你有帮助:
- 45个实用的JavaScript技巧、窍门和最佳实践
- python数据结构与算法——队列
- 准备写一些读书笔记,最近在填坑 SQL学习指南 Spring in Action effective Java
- 编译工程时报illegal character:\65279--转
- 山东省第五届ACM省赛
- Hibernate查询效率对比
- php 仿百度文库
- 学习C++语言的50条忠告
- vmware能够ping通内网,上不了外网的解决方法
- Android - 用Fragments实现动态UI - 创建Fragment
- First release of mlrMBO - the toolbox for (Bayesian) Black-Box Optimization
- Selenium自动化初级/中级网络授课班招生
- Python下的OpenCV学习 02 —— 图像的读取与保存
- 四十六、android中的Bitmap
- VS2015 新建 ASP.NET Web应用程序, 此模板尝试加载程序集‘Microsoft.VisualStudio.Web.Project’, 解决方案
- 【项目 &#183; WonderLand】 系 统 设 计
- Python3基础 filter+lambda 筛选出1-20之间的奇数
- 每天CSS学习之border-radius
- .NET Core容器化开发系列(一)——Docker里面跑个.NET Core
热门文章
- 基本的bash shell 命令
- GitHub 热点速览 Vol.23:前后端最佳实践
- mac 排查被占端口
- 使用redis实现nodejs并发服务
- 驱动开发 —— 从零开始(1) 配置vs20xx+wdkxx环境
- 我深爱的Java,对不起,我出轨了!!!呸!渣男!
- nodejs 换源
- SQL常用取整函数
- Centos7 composer安装时 Warning: This development build of composer is over 60 days old. It is recommended to update it by running ";/usr/bin/composer self-update"; to get the latest version.
- 基于web网站项目的性能测试结果分析