[ACM_模拟] UVA 10881 Piotr's Ants[蚂蚁移动 数组映射 排序技巧]

简介:


 

 

"One thing is for certain: there is no stopping them;
the ants will soon be here. And I, for one, welcome our
new insect overlords."

Kent Brockman

 

Piotr likes playing with ants. He has n of them on a horizontal pole L cm long. Each ant is facing either left or right and walks at a constant speed of 1 cm/s. When two ants bump into each other, they both turn around (instantaneously) and start walking in opposite directions. Piotr knows where each of the ants starts and which direction it is facing and wants to calculate where the ants will end up Tseconds from now.

Input
The first line of input gives the number of cases, NN test cases follow. Each one starts with a line containing 3 integers: L , T and n(0 <= n <= 10000) . The next n lines give the locations of the n ants (measured in cm from the left end of the pole) and the direction they are facing (L or R).

Output
For each test case, output one line containing "Case #x:" followed by n lines describing the locations and directions of the n ants in the same format and order as in the input. If two or more ants are at the same location, print "Turning" instead of "L" or "R" for their direction. If an ant falls off the pole beforeT seconds, print "Fell off" for that ant. Print an empty line after each test case.

Sample Input Sample Output
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

 


Problemsetter: Igor Naverniouk
Alternate solutions: Frank Pok Man Chu and Yury Kholondyrev

 

题目大意:一根长L的木棍上有n只蚂蚁,每只蚂蚁要么朝左爬,要么朝右爬,速度为1/s。当2只蚂蚁相撞时,二者同时掉头(掉头时间忽略不计)。每次给出蚂蚁的初始位置和朝向,计算T秒之后每只蚂蚁的位置。输入第一行为数据组数,每组数据第一行3个整数L,T,n ,以下n行描述一个蚂蚁的初始状态,其中整数x表示其距离木棍左端的距离,字母的初始朝向(L左,R右)

解题思路:从远处看就是一群密密麻麻的点在移动,当蚂蚁因为碰撞而掉头时,看上去和2点"对穿过去"没任何区别,换句话说如果把蚂蚁看成没有区别的小点,那么只需计算每只蚂蚁在T时刻的位置即可。如蚂蚁1=(1,R),蚂蚁2=(3,L),蚂蚁3=(4,L),则2秒钟之后,3只蚂蚁分别为(3,R),(1,L),(2,L)。

     掉头等价于穿过是整体而言,对于单个蚂蚁并不是。蚂蚁1的初始状态为(1,R)但是2秒钟之后有蚂蚁状态为(3,R)但不一定是蚂蚁1.换句话说就是要弄清楚哪只是哪只!

       又因为每只蚂蚁的相对位置是不变的,因此把所有目标位置从小到大排序,从左到右的每个位置对应初始状态下从左到右的每只蚂蚁。由于原题目中的蚂蚁不一定是按照从左到右的顺序输入,还需要预处理计算输出的第i只蚂蚁的序号order[i].

复制代码
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 10000+5;
 6 struct Ant{
 7     int id;//输入顺序
 8     int p;//位置
 9     int d;//朝向 -1:L;0:Turning;1:R
10     bool operator<(const Ant& a)const{
11         return p<a.p;
12     }
13     void set(int ID,int P,int D){
14         id=ID;p=P;d=D;
15     }
16 }before[maxn],after[maxn];
17 const char dirName[][10]={"L","Turning","R"};
18 int order[maxn];//输入的第i只蚂蚁是终态中的左数第order[i]只蚂蚁
19 int main(){
20     int K;
21     cin>>K;
22     for(int kase=1;kase<=K;kase++){
23         int L,T,n;
24         cin>>L>>T>>n;
25         for(int i=0;i<n;i++){
26             int p,d;
27             char c;
28             cin>>p>>c;
29             d=(c=='L' ? -1:1);
30             before[i].set(i,p,d);
31             after[i].set(0,p+T*d,d);
32         }
33         //计算order数组
34         sort(before,before+n);
35         for(int i=0;i<n;i++)
36             order[before[i].id]=i;
37         //计算终态
38         sort(after,after+n);
39         for(int i=0;i<n-1;i++)//修改碰撞中的,蚂蚁的方向
40             if(after[i].p==after[i+1].p)
41                 after[i].d=after[i+1].d=0;
42         //输出结果
43         printf("Case #%d:\n",kase);
44         for(int i=0;i<n;i++){
45             int a=order[i];
46             if(after[a].p<0 || after[a].p>L)printf("Fell off\n");
47             else printf("%d %s\n",after[a].p,dirName[after[a].d+1]);
48         }
49         printf("\n");
50     }return 0;
51 }
复制代码
相关文章
【基础算法】[PTA]-找出不是两个数组共有的元素
【基础算法】[PTA]-找出不是两个数组共有的元素
每日一题---1380. 矩阵中的幸运数[力扣][Go]
每日一题---1380. 矩阵中的幸运数[力扣][Go]
每日一题---1380. 矩阵中的幸运数[力扣][Go]
|
算法 Python
Python算法之动态规划(Dynamic Programming)解析:二维矩阵中的醉汉(魔改版leetcode出界的路径数)
现在很多互联网企业学聪明了,知道应聘者有目的性的刷Leetcode原题,用来应付算法题面试,所以开始对这些题进行“魔改”,比如北京某电商平台的这道题: 有一个正方形的岛,使用二维方形矩阵表示,岛上有一个醉汉,每一步可以往上下左右四个方向之一移动一格,如果超出矩阵范围他就死了,假设每一步的方向都是随机的(因为他是醉的),请计算n步以后他还活着的概率。
Python算法之动态规划(Dynamic Programming)解析:二维矩阵中的醉汉(魔改版leetcode出界的路径数)
LeetCode contest 182 5368. 找出数组中的幸运数
LeetCode contest 182 5368. 找出数组中的幸运数
|
Java Shell
Codeforces Round #746 (Div. 2) D - Hemose in ICPC ?(交互 二分 欧拉序)
Codeforces Round #746 (Div. 2) D - Hemose in ICPC ?(交互 二分 欧拉序)
154 0
|
Java Python
ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ
ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ
ACM 选手图解 LeetCode 搜索旋转排序数组Ⅱ
|
算法 Java Python
ACM 选手图解 LeetCode 路径总和
ACM 选手图解 LeetCode 路径总和
ACM 选手图解 LeetCode 路径总和
|
Java Python
ACM 选手图解 LeetCode 搜索旋转排序数组
ACM 选手图解 LeetCode 搜索旋转排序数组
ACM 选手图解 LeetCode 搜索旋转排序数组
☆打卡算法☆LeetCode 113、路径总和 II 算法解析
“给定一个二叉树根节点和目标整数,找出所有符合从根节点到目标节点的值等于目标值的路径。”