UVA 10881 Piotr's Ants（模拟）

题目链接：https://vjudge.net/problem/UVA-10881

其实这道题的关键只有一句话：

　　　当两个蚂蚁因碰撞而掉头的时候，我们完全可以认为是两个点对穿而过。

这时候我们的主要任务就是弄清楚“谁是谁”。

然而很明显每只蚂蚁的相对顺序是不变的，所以我们要记录一个$order$数组。

预处理出它的初始状态和order，同时算出走之后的状态。

注意程序中的有些地方处理的很巧妙。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 struct node{

     int id;

     int pos;

     int dir;

     bool operator < (const node& a) const{

         return pos<a.pos;

     }

 } before[maxn],after[maxn];

 const char dirname[][]={"L","Turning","R"};

 int order[maxn];

 int main(){

     int kase;

     scanf("%d",&kase);

     for(int k=;k<=kase;k++){

         int L,T,n;

         printf("Case #%d:\n",k);

         scanf("%d%d%d",&L,&T,&n);

         for(int i=;i<n;i++){

             int p,d;

             char c;

             scanf("%d %c",&p,&c);

             d=(c=='L'?-:);

             before[i]=(node){i,p,d};

             after[i]=(node){,p+d*T,d};

         }

         sort(before,before+n);

         for(int i=;i<n;i++) order[before[i].id]=i;

         sort(after,after+n);

         for(int i=;i<n-;i++)

             if(after[i].pos==after[i+].pos) after[i].dir=after[i+].dir=;

         for(int i=;i<n;i++){

             int a=order[i];

             if(after[a].pos<||after[a].pos>L) printf("Fell off\n");

             else printf("%d %s\n",after[a].pos,dirname[after[a].dir+]);

         }

         printf("\n");

     }

     return ;

 } 

AC代码