1.题目描述：点击打开链接
2.解题思路：本题是一道很经典的题目，锻炼思维的。蚂蚁在杆子上相互碰撞，反弹，从远处看去，好像直接穿过，除此之外，每只蚂蚁的相对位置是不变的。本题就是从这两处突破口编程解决的。因此，我们可以最初把他们看做直接穿过，到最后再确定他们”谁是谁“即可。由于最初输入时是乱序（没有按照位置由小到大输入），因此应该先记录输入的序号，按照位置排序后用一个order数组标记第i个输入的蚂蚁按照位置由小到大的正确序号，那么即使经过Ts后，这个顺序也是固定的。这样就能找到每只蚂蚁的终态了。详细过程见代码。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 10000+5struct Ant{int id, p, d;//id是输入顺序，p是位置，d是朝向：-1朝左，0转身中，1朝右bool operator < (const Ant&a)const{return p < a.p;}}before[N],after[N];const char dir[][10] = { "L", "Turning", "R" };int order[N];//输入的第i只蚂蚁是终态中的左数第order[i]只蚂蚁int main(){//freopen("t.txt", "r", stdin);int k;cin >> k;for (int rnd = 1; rnd <= k; rnd++){int L, T, n;printf("Case #%d:\n", rnd);cin >> L >> T >> n;for (int i = 0; i < n; i++){int p, d;char c;cin >> p >> c;d = (c == 'L' ? -1 : 1);before[i] = Ant{ i, p, d };after[i] = Ant{ 0, p + T*d, d };//id未知，先都设为0}sort(before, before + n);for (int i = 0; i < n; i++)order[before[i].id] = i;//记录按照位置排序后的序号sort(after, after + n);//排序后得到Ts时各个蚂蚁的位置，此时也是各个蚂蚁终态的位置for (int i = 0; i < n-1;i++)if (after[i].p == after[i + 1].p)//位置恰好重合，说明正在转向，，修改方向after[i].d = after[i + 1].d = 0;for (int i = 0; i < n; i++){int a = order[i];//输入的第i只蚂蚁的终态序号if (after[a].p<0 || after[a].p>L)printf("Fell off\n");else printf("%d %s\n", after[a].p, dir[after[a].d + 1]);//把d加1，对应数组中的字符串}cout << endl;}return 0;}
人若勇敢就是自己最好的朋友
