题面
??“One thing is for certain: there is no stopping them; the ants will soon be here. And I, for one, welcome our new insect overlords.” ——Kent Brockman
??Piotr likes playing with ants. He has n of them on a horizontal pole L cm long. Each ant is facing either left or right and walks at a constant speed of 1 cm/s. When two ants bump into each other, they both turn around (instantaneously) and start walking in opposite directions. Piotr knows where each of the ants starts and which direction it is facing and wants to calculate where the ants will end up T seconds from now.
题意
??有n只蚂蚁在一个长为
L 的棍子上，每只蚂蚁一开始有一个朝向L/R ，问T秒后各蚂蚁所在的位置以及朝向（两只蚂蚁相撞后反向）
解法
排序：
相信这道题大家都看过了。其实只要知道一个结论这道题就很容易做了：移动前后，各蚂蚁的相对位置不变——①
因此，这道题的重点就不是求位置了，而是求出位置所代表的蚂蚁，所以可以将蚂蚁碰撞视作为蚂蚁互相穿过。
先将给出的蚂蚁按位置排序，然后记录下编号为i 的蚂蚁的排名rki，因为①，所以移动后i蚂蚁的排名仍然是rki ，于是根据初始朝向直接求出各蚂蚁在T秒后的位置，然后对于第i 只蚂蚁，它最终的位置就是移动后的第rki个位置
拓展
分析
??独木桥代码：https://gitee.com/qjlyh/codes/1hibnal8o6cv2rdjgqfk357
??独木桥数据：https://pan.baidu.com/s/1dF1tFhv
复杂度
O（Knlogn），K<script type="math/tex" id="MathJax-Element-28">K</script>为数据组数
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Lint long long int
using namespace std;
const int MAXN=10010;
struct node
{int id,x,p;bool operator < (const node &a) const{return x<a.x;}
}p[MAXN],q[MAXN];
int rk[MAXN];
int T,L,R,n;
int main()
{char cs;int x,d;scanf("%d",&T);for(int k=1;k<=T;k++){printf("Case #%d:\n",k);scanf("%d%d%d",&L,&R,&n);for(int i=1;i<=n;i++){scanf("%d %c",&x,&cs);d= cs=='L' ? -1 : 1 ;p[i]=(node){ i,x,d };q[i]=(node){ 0,x+R*d,d };}sort( p+1,p+n+1 );for(int i=1;i<=n;i++) rk[p[i].id]=i;sort( q+1,q+n+1 );for(int i=1;i<=n-1;i++)if( q[i].x==q[i+1].x ) q[i].p=q[i+1].p=0;for(int i=1;i<=n;i++){x=rk[i];if( q[x].x<0 || q[x].x>L ) printf("Fell off\n");else{printf("%d ",q[x].x);if( q[x].p==-1 ) printf("L\n");elseif( !q[x].p ) printf("Turning\n");else printf("R\n");}}printf("\n");}return 0;
}