题目链接
https://vjudge.net/problem/UVA-10881
题意
一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。每组最后输出一个空行。
分析
把蚂蚁看作车，两只蚂蚁相撞时等效为两辆车的驾驶员互换（车的朝向不变）。这样n辆车的最终位置是唯一确定的，问题转化成了求n个驾驶员与n辆车的映射。
两辆车要相撞肯定得朝不同方向行驶，用集合l表示朝右行驶的车，用集合r表示朝左行驶的车。
对于l中的每一辆车x，穷举r中的每一辆车y与x比较看是否相撞，即是否互换驾驶员。经过穷举后，n辆车的最终驾驶员就确定下来了。
解题
（1）构造结构体数组a，a中存放n辆车的位置、朝向、驾驶员编号。
（2）对结构体按相对位置从小到大排序
（3）计算驾驶员的互换情况
（4）求出n辆车的最终位置
（5）对结构体按驾驶员编号从小到大排序
（6）输出答案
代码
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#include <map>using namespace std;
const int maxn=1e4+100;
struct ant
{int num,pos,sub;char dir;
} a[maxn];
stack<ant> l; //朝向右边的蚂蚁
ant r[maxn]; //朝向左边的蚂蚁
map<int,int> m;
bool cmp1(const ant &t1,const ant &t2)
{return t1.pos<t2.pos;
}
bool cmp2(const ant &t1,const ant &t2)
{return t1.num<t2.num;
}int main()
{int t,d=1,tot=0;scanf("%d",&t);while(t--){int L,T,n;m.clear();tot=0;scanf("%d%d%d",&L,&T,&n);for(int i=0; i<n; i++){scanf("%d %c",&a[i].pos,&a[i].dir);a[i].num=i;}sort(a,a+n,cmp1);for(int i=0; i<n; i++){a[i].sub=i;}while(!l.empty()) l.pop();for(int i=0; i<n; i++)if(a[i].dir=='R')l.push(a[i]);elser[++tot]=a[i];while(!l.empty()){ant x=l.top();l.pop();for(int i=1; i<=tot; i++){ant y=r[i];if(x.pos>y.pos) continue;if(x.pos+T>=y.pos-T){swap(a[x.sub].num,a[y.sub].num);}}}for(int i=0; i<n; i++){a[i].pos+=a[i].dir=='R'?T:-T;m[a[i].pos]++;}sort(a,a+n,cmp2);printf("Case #%d:\n",d++);for(int i=0; i<n; i++){if(a[i].pos>L || a[i].pos<0)printf("Fell off\n");else if(m[a[i].pos]>1)printf("%d %s\n",a[i].pos,"Turning");elseprintf("%d %c\n",a[i].pos,a[i].dir);}printf("\n");}return 0;
}