UVA 10881 - Piotr's Ants【模拟+思维】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=10000+5;
 4 struct Ant
 5 {
 6     int id;//顺序
 7     int p;//位置
 8     int d;//转向,-1表示左,0表示碰撞中,1表示右
 9     bool operator <(const Ant& a)const
10     {
11         return p<a.p;
12     }
13 }before[maxn],after[maxn];
14 const char dirName[][10]={"L","Turning","R"};
15 int order[maxn];//输入的第i只蚂蚁是终态中的左数第order[i]只蚂蚁
16 int main()
17 {
18     int K;
19     scanf("%d",&K);
20     for(int kase=1;kase<=K;kase++)
21     {
22         int L,T,n;
23         scanf("%d%d%d",&L,&T,&n);
24         for(int i=0;i<n;i++)
25         {
26             int p,d;
27             char c;
28             scanf("%d %c",&p,&c);
29             d=(c=='L'?-1:1);
30             before[i]=(Ant){i,p,d};
31             after[i]=(Ant){0,p+T*d,d};//所有的蚂蚁相撞后可以看做对穿而过,这里的id是未知的
32         }
33         printf("Case #%d:\n",kase);
34         //计算order数组
35         sort(before,before+n);
36         for(int i=0;i<n;i++)//最巧妙的地方在这里，第一次从左到右所有的蚂蚁的相对位置没有变化
37             order[before[i].id]=i;
38         //计算终态
39         sort(after,after+n);
40         for(int i=0;i<n-1;i++)//修改碰撞中的蚂蚁的方向
41             if(after[i].p==after[i+1].p)
42                 after[i].d=after[i+1].d=0;
43         //输出结果
44         for(int i=0;i<n;i++)
45         {
46             int a=order[i];
47             if(after[a].p<0||after[a].p>L)
48                 printf("Fell off\n");
49             else printf("%d %s\n",after[a].p, dirName[after[a].d+1]);
50         }
51         printf("\n");
52     }
53     return 0;
54 }