【题解】UVa 10881【Piotr’s Ants】

分析

这里就是一道模拟题了,比较经典,因为两个蚂蚁碰头和传过去其实没啥区别。

代码

#include<cstdio>
#include<algorithm>
using std::sort;
const int MAXN = 10000 + 6;

class Ant{
public:
    int id;
    int p;
    int d;

    bool operator < (const Ant &a) const {
        return p < a.p;
    }
};
Ant before[MAXN],after[MAXN];

const char dirName[][10] = {"L","Turning","R"};
int order[MAXN];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out2.txt","w",stdout);
    int K;scanf("%d",&K);
    for(int Case = 1;Case <= K;Case++){
        int L,T,n;
        printf("Case #%d:\n",Case);
        scanf("%d %d %d",&L,&T,&n);
        for(int i = 0;i < n;i++){
            int p,d;char c;
            scanf("%d %c",&p,&c);
            d = (c == 'L' ? -1 : 1);
            before[i] = (Ant){i,p,d};
            after[i] = (Ant){0,p + T * d,d};
        }

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

        sort(after,after + n);
        for(int i = 0;i < n - 1;i++)
            if(after[i].p == after[i + 1].p) after[i].d = after[i + 1].d = 0;

        for(int i = 0;i < n;i++){
            int a = order[i];
            if(after[a].p < 0 || after[a].p > L) printf("Fell off\n");
            else printf("%d %s\n",after[a].p,dirName[after[a].d + 1]);
        }
        printf("\n");
    }

    return 0;
}