uva 10881 - Piotr's Ants

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1822

关键思路：

是UVa 10714 - Ants的加强版本

关键在于理解，不管走多久，蚂蚁的相对顺序都是不变的，还有两只蚂蚁相碰之后，看起来就和“穿过去”一样。

而最终每只蚂蚁的方向，就和每只蚂蚁按照原来方向一直走T秒之后，这时候从左到右每只蚂蚁的方向，就是初始时从左到右的每只蚂蚁T秒后的方向。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;

const int maxn = 10000+10;
int L, T, n;

struct node{
    int len;
    int dir;
    int id;
    int rank;
    friend bool operator<(const node&a,const node&b){
        return a.len < b.len;
    }
}arr[maxn];

struct Rank{
    int len;
    int dir;
    friend bool operator < (const Rank&a,const Rank&b){
        return a.len < b.len;
    }
}tmp[maxn];

char new_dir[maxn];

map<int,int>mp;

bool cmp(const node&a,const node&b){
    return a.id < b.id;
}


int main(){

    int nCase, cas=1;
    char ch[2];

    scanf("%d", &nCase);

    while(nCase--){
        scanf("%d%d%d",&L, &T, &n);

        for(int i=0; i<n; ++i){
            scanf("%d %s",&arr[i].len, ch);
            arr[i].id = i;
            if(ch[0]=='R') arr[i].dir = 1;
            else arr[i].dir = -1;
        }
        
        sort(arr, arr+n);

        mp.clear();
        for(int i=0; i<n; ++i){
            arr[i].rank = i;
            tmp[i].len = arr[i].len+arr[i].dir*T;
            tmp[i].dir = arr[i].dir;

            if(mp.find(tmp[i].len) == mp.end()){
                mp[tmp[i].len] = 1;

            }else{
                ++mp[tmp[i].len];
            }
        }

        sort(tmp, tmp+n);
        for(int i=0; i<n; ++i)
            new_dir[i] = tmp[i].dir<0?'L':'R';

        for(int i=0; i<n; ++i)
            arr[i].len = tmp[i].len;
        sort(arr, arr+n, cmp);

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

        for(int i=0; i<n; ++i){
            if(arr[i].len < 0 || arr[i].len > L) 
                puts("Fell off");
            else if(mp[arr[i].len] > 1)
                printf("%d Turning\n", arr[i].len);
            else
                printf("%d %c\n", arr[i].len, new_dir[arr[i].rank]);
        }
        puts("");
    }

    return 0;
}