uva10881 Piotr's Ants<排序>

链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1822

题意:

一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时转向（转向时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置;

思路:

对于蚂蚁来说, 如果把它们看成是没有区别的小点，那么只需独立计算出每只蚂蚁在T时刻的位置即可;

比如，有3只蚂蚁，蚂蚁1=(1, R)，蚂蚁2= (3, L)，蚂蚁3=(4, L)，则两秒钟之后，3只蚂蚁分别为 1=(3,R)、2= (1,L)和 3= (2,L), 这是不转向的结果;

如果转向其结果应该为1=(1, L) , 2=(2, L), 3=( 3, R );即按位置排个序,就是它们对应的新位置;

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 const int M= 10000+10;
 9 const char s[][10]={"L", "Turning", "R"};// 
10 int t[M];//记录相对位置,输入的第i只蚂蚁是终态中的左数第t[i]只蚂蚁
11 struct Ant
12 {
13     int n, p, d;// d 记录朝向。 -1: 左; 0:转身中; 1:右
14 }a[M],b[M];
15 bool cmp( const Ant &a, const Ant &b )
16 {
17     return a.p<b.p;    
18 }
19 int main( )
20 {    int K, L, T, N, x, y;
21     char c[3];
22     scanf( "%d", &K );
23     for( int Case=1; Case<=K; ++Case ){
24         scanf( "%d%d%d", &L, &T, &N );
25         for( int i=0; i<N; ++ i ){
26             scanf( "%d%s", &x, c );
27             y=(c[0]=='R'?1:-1);
28             a[i]=(Ant){i,x, y};
29             b[i]=(Ant){0, x+T*y, y};    
30         }
31         sort( a, a+N, cmp );
32         sort( b, b+N, cmp );
33         for( int i=0; i<N; ++ i )
34             t[a[i].n]=i;
35         for( int i=0; i<N-1; ++ i )
36             if(b[i].p==b[i+1].p) b[i].d=b[i+1].d=0;    // 判断结束时是否正好相遇 
37         printf( "Case #%d:\n", Case );    
38         for( int i=0; i<N; ++ i ){
39             int temp=t[i];
40             if( b[temp].p<0||b[temp].p>L ) puts( "Fell off" );
41             else printf( "%d %s\n", b[temp].p, s[b[temp].d+1] );
42         }
43         puts("");
44     }
45     return 0;
46 }