UVA 10881 Piotr's Ants

训练指南上的一道题目，感觉还不错。

参考该书做如下总结：

题意：一根长度为L的木棍上有n只蚂蚁，每只蚂蚁要么朝左要么朝右爬，求T秒后每只蚂蚁的位置和状态。

分析：1）蚂蚁相撞“掉头”等价于“对穿而过”；

　　 2）每只蚂蚁最后位置固定；

　　 3）初始时按位置排序后，第i只蚂蚁不可能比第i+1只蚂蚁的距离远。

View Code

 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <sstream>
 8 #include <iostream>
 9 #include <cmath>
10 #include <cstring>
11 #include <algorithm>
12 #include <string>
13 #include <utility>
14 #include <vector>
15 #include <queue>
16 #include <stack>
17 #include <map>
18 #include <set>
19 using namespace std;
20 
21 typedef long long ll;
22 #define DEBUG(x) cout<< #x << ':' << x << endl
23 #define REP(i,n) for(int i=0;i < (n);i++)
24 #define PII pair<int,int>
25 #define PB push_back
26 #define MP make_pair
27 #define FI first
28 #define SE second
29 #define lowbit(x) (x&(-x))
30 #define INF (1<<30)
31 
32 struct piotr
33 {
34     int id;
35     int dis;
36     char dire;
37     bool operator < (const piotr& a) const {
38         return dis < a.dis;
39     }
40 }sta[10010],end[10010];
41 int order[10010];
42 int main()
43 {
44     #ifndef ONLINE_JUDGE
45     freopen("in","r",stdin);
46     #endif
47     int T;
48     int cas = 0;
49     scanf("%d",&T);
50     while(T--)
51     {
52         printf("Case #%d:\n",++cas);
53         int l,t,n;
54         scanf("%d%d%d",&l,&t,&n);
55         REP(i,n)
56         {
57             int dis;
58             char D[2];
59             scanf("%d%s",&dis,D);
60             int d = (D[0] == 'L'?-1:1);
61             sta[i] = (piotr){i,dis,D[0]};
62             end[i] = (piotr){0,dis+t*d,D[0]};
63         }
64         sort(sta,sta+n);
65         sort(end,end+n);
66         REP(i,n)order[sta[i].id]=i;
67         REP(i,n-1)
68             if(end[i].dis == end[i+1].dis)end[i].dire=end[i+1].dire='t';
69         REP(i,n)
70         {
71             int a = order[i];
72             if(end[a].dis<0 || end[a].dis>l)puts("Fell off");
73             else
74             {
75                 printf("%d ",end[a].dis);
76                 if(end[a].dire == 't')puts("Turning");
77                 else printf("%c\n",end[a].dire);
78             }
79         }
80         puts("");
81     }
82     return 0;
83 }