题目地址：http://vjudge.net/problem/UVA-10881
思路来自刘汝佳
从远远地看，蚂蚁掉头可以看成蚂蚁互相穿过，没有回头
所以把蚂蚁看成没有意义的小点，那么所有蚂蚁的位置都能确定了
还要知道哪一只蚂蚁是哪一只：
因为蚂蚁的相对位置是不变的，所以可以根据一开始的顺序判断位置变了之后的蚂蚁的序号
至于之后蚂蚁的方向同上述方法一样
流程：
1 走之前 蚂蚁位置从小到大排序，记下蚂蚁的顺序（该蚂蚁的序号就是结果蚂蚁的序号）
2计算T s后的蚂蚁的位置
3排序走之后蚂蚁的序号，此时蚂蚁的序号就是一开始蚂蚁的序号
4处理结果，因为是要按照input顺序
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=10000+5;
struct Ant
{int p,t,idx; //position,toward,idxbool operator < (const Ant& ant) const {return p>ant.p;}
}before[maxn],after[maxn];
int order[maxn];
const char dir[][11]={"L","Turning","R"};
int main(int argc, char const *argv[])
{int N,kase=0,p,n,T,L; char t;cin>>N;while(N--){cin>>L>>T>>n;for(int i=0;i<n;i++){scanf("%d %c",&p,&t);before[i]=Ant{p,t=='R'?1:-1,i};after[i]=Ant{p+(t=='R'?1:-1)*T,t=='R'?1:-1,0};}sort(before,before+n);for(int i=0;i<n;i++)order[before[i].idx]=i;sort(after,after+n);for(int i=0;i<n-1;i++)if(after[i].p==after[i+1].p) after[i].t=after[i+1].t=0;printf("Case #%d:\n", ++kase);for(int i=0;i<n;i++){int d=order[i];if(after[d].p>L||after[d].p<0) printf("Fell off\n");else printf("%d %s\n", after[d].p,dir[after[d].t+1]);}cout<<endl;}return 0;
}