数学有棵“数”，叫“奥数”，我想很多人，都在这个“数”上，羁绊过。今天就和大家分享下用算法解决奥数的一些小问题，请看题目：     一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。

别着急找纸笔，且看如何运用电脑去计算。为方便说明，我这样设定下~

【输入格式】

输入的第一行为数据组数。每组数据的第一行为3个正整数L, T,n（0≤n≤10 000）；以下n行每行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。

【输出格式】

对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turning表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。

【样例输入】

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

【分析】

假设你在远处观察这些蚂蚁的运动，会看到什么？一群密密麻麻的小黑点在移动。由于黑点太小，所以当蚂蚁因碰撞而掉头时，看上去和两个点“对穿而过”没有任何区别，换句话说，如果把蚂蚁看成是没有区别的小点，那么只需独立计算出每只蚂蚁在T时刻的位置即可。比如，有3只蚂蚁，蚂蚁1=(1, R)，蚂蚁2= (3, L)，蚂蚁3=(4, L)，则两秒钟之后，3只蚂蚁分别为(3,R)、(1,L)和(2,L)。

注意，虽然从整体上讲，“掉头”等价于“对穿而过”，但对于每只蚂蚁而言并不是这样。蚂蚁1的初始状态为(1,R)，因此一定有一只蚂蚁在两秒钟之后处于(3,R)的状态，但这只蚂蚁却不一定是蚂蚁1。换句话说，我们需要搞清楚目标状态中“谁是谁”。

也许读者已经发现了其中的奥妙：所有蚂蚁的相对顺序是保持不变的，因此把所有目标位置从小到大排序，则从左到右的每个位置对应于初始状态下从左到右的每只蚂蚁。由于原题中蚂蚁不一定按照从左到右的顺序输入，还需要预处理计算出输入中的第i只蚂蚁的序号order[i]。完整代码如下。

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

复制代码

运行效果：

[

完全看不懂 :lol。。。