学步园

这道题目也是非常有意义的。题目描述是这样的，一群小蚂蚁在一个竹竿上爬啊爬。遇到了另外一只蚂蚁的时候他们就碰头了，一碰头他们原来走的方向就变成相反的方向。

如果按照模拟题目来做的话，好像能做，但是我是个小菜鸟，敲出来之后发现不能成功，有很多地方实现不了，一会看看别人的代码，有没有人用模拟写。

现在我要说的是算法书上说的方法，很新奇，也很理智呀！这就是深度的思考，和随便看看的人的区别。

第一、需要注意的是，不管蚂蚁怎么运动他们的相对位置是不改变的，就是说，他不管怎么运动，他是第一，他永远是第一，当然这就要我们把蚂蚁掉下去也看成是在不存在的竹竿上运动。这样一来就一目了然了。方法也就出来了。

第二、蚂蚁碰头，也就是相当于穿过。只不过穿过的同时，他们两个蚂蚁也互换了。当然我们不能模拟两个蚂蚁互换。我们只能利用上面第一条观察所得：即相对位置是不发生改变的。

第三、方法也就出来了，就是既然他们的相对位置不发生变化，那么我其实的每个蚂蚁的位置信息都记住，然后我就把每个蚂蚁经过T时间后的位置都求出来，然后排下序，就又可以得到他们的相对的位置了，那么这就解决了，我知道了他们起始的信息，然后对应找一找就解决了问题。这个思路真的不错，我会及时的复习的。

贴出代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAXN = 10011;

struct Ant
{
	int id;
	int pos;
	int state; // -1:向左 0:turning 1:向右 
	
	bool operator < (const Ant &t) const  //按输入坐标的顺序排序. 
	{
		return pos < t.pos;
	}
}before[MAXN], after[MAXN];

char dir[3][10] = {"L", "Turning", "R"};

int order[MAXN];//order[i] = j的含义就是第i个输入的在第j个位置(当然是排序后的);

int L, T, n;

int main()
{
	int pos;
	char c;
	int d;
	int K;
	scanf("%d", &K);
	for (int cas = 1; cas <= K; cas++)
	{
		scanf("%d%d%d", &L, &T, &n);
		for (int i = 0; i < n; i++)
		{
			scanf("%d %c", &pos, &c);
			
			d = (c == 'R') ? 1 : -1;
			
			before[i] = (Ant){i, pos, d};
			after[i] = (Ant){0, pos + T * d, d};
		}
		sort(before, before + n);
		for (int i = 0; i < n; i++)
		{
			order[before[i].id] = i; //第id个输入的在排序后的i位置. 
		}
		sort(after, after + n);
		for (int i = 0 ; i < n - 1; i++)
		{
			if (after[i].pos == after[i + 1].pos)
			{
				after[i].state = after[i + 1].state = 0;
			}
		}
		printf("Case #%d:\n", cas);
		for (int i = 0; i < n; i++) //要按输入的顺序输出各个蚂蚁的顺序. 
		{
			int a = order[i];
			if (after[a].pos < 0 || after[a].pos > L)
			{
				printf("Fell off\n");
				continue;
			}
			else
			{
				printf("%d %s\n", after[a].pos, dir[after[a].state + 1]);
			}
		}
		printf("\n");

	}
//	system("pause");
	return 0;
}