UVa 10881 蚂蚁

题意：

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

思路：

首先，如果不考虑掉头的话，蚂蚁相遇时就是对穿而过，如果考虑掉头，局势是不会发生改变的，就是蚂蚁的位置不同。

比如蚂蚁1（2，R），蚂蚁2（4，L），经过3秒后，如果不考虑掉头，那么蚂蚁1（5，R），蚂蚁2（1，L）。如果考虑掉头，则蚂蚁1（1 , L），蚂蚁2（5 , R）。也就是说不管怎样，总有蚂蚁会在（1，L），也总有蚂蚁会在（5，R），所以一开始我们可以不用考虑掉头来计算出所有蚂蚁最后的状态，我们需要确定的就是哪只蚂蚁处于这个状态。

接下来的一点很重要，因为蚂蚁相撞后会掉头，所以蚂蚁的相对顺序是不会变的，也就是说最左边的蚂蚁肯定一直在最左边，从左往右第1只蚂蚁也肯定一直处于第1只...这个想一下就可以理解了。

既然这样，最后只需要按照坐标排序然后和蚂蚁匹配就可以了。

 1 #include<iostream> 
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int l, t, n;
 6 
 7 const int maxn = 10000 + 5;
 8 
 9 struct node
10 {
11     int id;
12     int p;
13     int d;    //方向，-1表示往左，0表示碰撞，1表示往右
14     bool operator <(const node& rhs)  const
15     {
16         return p < rhs.p;
17     }
18 }before[maxn],after[maxn];
19 
20 int order[maxn];
21 
22 char dir[][10] = { "L", "Turning", "R" };
23 
24 int main()
25 {
26     ios::sync_with_stdio(false);
27     //freopen("D:\txt.txt", "r", stdin);
28     int T;
29     int p;
30     char c;
31     int kase = 0;
32     cin >> T;
33     while (T--)
34     {
35         cin >> l >> t >> n;
36         for (int i=0; i < n; i++)
37         {
38             cin >> p >> c;
39             int d = c == 'L' ? -1 : 1;
40             before[i].id = i;
41             before[i].p = p;
42             before[i].d = d;
43             after[i].id = 0;
44             after[i].p = t*d + p;
45             after[i].d = d;
46         }
47         sort(before, before + n);
48         for (int i = 0; i < n; i++)
49         {
50             order[before[i].id] = i;
51         }
52 
53         sort(after, after + n);
54         for (int i = 0; i < n;i++)
55         if (after[i].p == after[i + 1].p)
56             after[i].d = after[i + 1].d = 0;
57 
58         cout << "Case #" << ++kase << ":" << endl;
59         for (int i = 0; i < n; i++)
60         {
61             int num = order[i];
62             if (after[num].p<0 || after[num].p>l)   cout << "Fell off" << endl;
63             else cout << after[num].p << " " << dir[after[num].d + 1] << endl;
64         }
65         cout << endl;
66     }
67 }