cogs 1456. [UVa 10881,Piotr's Ants]蚂蚁
2024-09-06 00:06:17
1456. [UVa 10881,Piotr's Ants]蚂蚁
★ 输入文件:Ants.in
输出文件:Ants.out
简单对比
时间限制:1 s 内存限制:128 MB
【题目描述】
- 一根长度为L厘米的木棍上有n只蚂蚁,每只蚂蚁要么往左爬要么往右爬,速度为1cm/s。当两只蚂蚁相遇时,二者同时掉头(掉头时间忽略不计)。给出每只蚂蚁的初始位置和朝向,计算T秒之后蚂蚁的位置。
【输入格式】
- 输入第一行为数据组数。每组第一行为三个整数L,T,n(n≤10 000);以下n行描述一只蚂蚁的初始位置,其中,整数x为蚂蚁距左端的距离(单位:厘米),字母表示初始朝向(L向左,R向右)。
【输出格式】
对于每组数据,输出n(Case #n:),按输入顺序输出每只蚂蚁的位置和朝向(Turning表示正在碰撞)。在T秒之前已经掉落的蚂蚁(正好爬到边缘不算)输出Fell off
【样例输入】
2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R
【样例输出】
Case #1:
2 Turning
6 R
2 Turning
Fell off
Case #2:
3 L
6 R
10 R
【来源】
UVa 10881,Piotr's Ants
思路:
假设你在远处观察这些蚂蚁的运动,会看到什么?一群密密麻麻的小黑点在移动。由于黑点太小,所以当蚂蚁一碰撞而掉头时,看上去和两个点”对穿而过“没有什么区别。换句话说,如果把蚂蚁看做是没有区别的小点,那么只需要计算出每只蚂蚁在T时刻的位置即可。比如,有3只蚂蚁,蚂蚁1=(1,R),蚂蚁2=(3,L),蚂蚁3=(4,L),则两秒之后,三只蚂蚁分别为(3,R),(1,L)和(2,L)。
注意,虽然从整体上讲,”掉头“等价于”对穿而过“,但对于每只蚂蚁而言,并不是这样。蚂蚁1的初始状态为(1,R),因此一定有一只蚂蚁在两秒钟之后处于(3,R)的状态,但这只蚂蚁却不一定是蚂蚁1.换句话说,我们需要搞清楚目标状态中的”谁是谁“。
可以想象一下,所有蚂蚁的相对顺序是保持不变的。然后这个问题就很好解决了。
这是代码:
#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 10001
using namespace std;
map<int,int>vis;
int T;
int len,t,n,num;
struct nond{
int pos,turn,id;
}v[MAXN],vv[MAXN];
int cmp(nond a,nond b){
return a.pos<b.pos;
}
int cmp1(nond a,nond b){
return a.id<b.id;
}
int main(){
freopen("Ants.in","r",stdin);
freopen("Ants.out","w",stdout);
scanf("%d",&T);
for(int k=;k<=T;k++){
vis.clear();
memset(v,,sizeof(v));
memset(vv,,sizeof(vv));
printf("Case #%d:",k);
scanf("%d%d%d",&len,&t,&n);
for(int i=;i<=n;i++){
char c;
scanf("%d %c",&v[i].pos,&c);
if(c=='R') v[i].turn=;
else v[i].turn=-;
v[i].id=i;vv[i]=v[i];
}
sort(v+,v++n,cmp);
sort(vv+,vv++n,cmp);
for(int i=;i<=n;i++){
if(vv[i].turn==-) vv[i].pos-=t;
else if(vv[i].turn==) vv[i].pos+=t;
if(vv[i].pos>len||vv[i].pos<) vv[i].turn=;
else vis[vv[i].pos]++;
}
sort(vv+,vv++n,cmp);
for(int i=;i<=n;i++){
v[i].pos=vv[i].pos;
v[i].turn=vv[i].turn;
}
sort(v+,v++n,cmp1);
for(int i=;i<=n;i++){
if(v[i].turn==) cout<<"Fell off"<<endl;
else if(vis[v[i].pos]!=) cout<<v[i].pos<<" "<<"Turning"<<endl;
else if(v[i].turn==) cout<<v[i].pos<<" "<<"R"<<endl;
else cout<<v[i].pos<<" "<<"L"<<endl;
}
}
}
最新文章
- Java中的Socket的用法
- 那些过目不忘的H5页面
- web 音频文件自动播放(兼容所有浏览器)
- jvm分析
- Linux下第一次使用MySQL数据库,设置密码
- js基础知识之_对象
- 多线程 - 线程同步锁(lock、Monitor)
- The 5th tip of DB Query Analyzer
- 使用Java中间MessageDigest该文本MD5加密(Java中间MD5样品加密算法演示)
- 解决mysql 1062 主从错误
- 一起来学linux:目录与路径
- thinkphp系列:类的自动加载是如何设计的
- 自学Python全栈开发第一次笔记
- Linux查询一台机器的IP地址和其对应的域名
- 数据库获取map数据后转化成json格式的数据
- Hibernate查询,返回new对象(注意这个新定义的类要有构造函数),使用sql带条件分页查询并且把结果显示到一个对象的集里面的解决方案
- 任意N个不同数的逆序对平均值
- 谷歌浏览器隐藏url前缀问题
- Python3+SQLAlchemy+Sqlite3实现ORM教程
- Vue-详解设置路由导航的两种方法: <;router-link :to=";...";>; 和router.push(...)
热门文章
- 深入理解Android之Java虚拟机Dalvik
- PHP 二维数组去掉重复值并保持原结构
- poj--3620--Avoid The Lakes(dfs)
- nyoj--767--因子和(模拟)
- Gcc/MinGW/Cygwin/Msys 分别是什么?
- IE9+ BUG汇总
- OpenGL编程逐步深入(五)Uniform 变量
- python2中打印列表与字典内的中文字符
- JavaScript:理解prototype与__proto__,原型与原型链
- CF817F MEX Queries(线段树上二分)