uva 10881 Piotr's Ants

https://vjudge.net/problem/UVA-10881

题意：

一根长为L cm的木棍上有很多只蚂蚁，他们的速度为1cm每秒，他们的有的向右，有的向左。当两只蚂蚁相撞的时候，他们各自掉头往回走，碰撞的时间可以忽略不记。

现在给出若干只蚂蚁起始时刻的位置和方向，问经过t秒钟后，这些蚂蚁的位置和朝向。

思路：

很脑洞的一道题，如果我们忽略蚂蚁的编号就可以发现，每只蚂蚁是没有区别的，即两只蚂蚁的碰撞可以看成他们直接穿过。

那么我们就可以方便的计算每只蚂蚁的最终位置了。

之后需要想到的是，不忽略每只蚂蚁的编号那么每只蚂蚁的顺序是固定的（这个需要好好理解），因为一只蚂蚁如果位于两只蚂蚁的中间，如果他们不相撞，那么肯定始终是在中间的；如果相撞的话，就一直来回来回的碰碰碰。。。。2333

所以是一直在中间的，那么这方便我们计算每只蚂蚁经过t时刻之后的朝向，这可以看成是每只蚂蚁状态的传递。

由于输入的时候不是按照从左到右的顺序输入的，所以我们需要用一个数组来保存位置。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct node
{
    int id;
    int p;
    int sta;

    bool operator < (const node& rhs) const
    {
        return p < rhs.p;
    }
} before[10005],after[10005];

int ord[10005];

int main()
{
    int cas;

    scanf("%d",&cas);

    for (int k = 1;k <= cas;k++)
    {
        int l,t,n;

        scanf("%d%d%d",&l,&t,&n);

        for (int i = 0;i < n;i++)
        {
            int p;
            char c;
            int d;

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

            if (c == 'R') d = 1;
            else d = -1;

            before[i] = node{i,p,d};
            after[i] = node{-1,p + t * d,d};
        }

        sort(before,before + n);

        for (int i = 0;i < n;i++)
            ord[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].sta = after[i+1].sta =  0;//正在相撞
        }

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

        for (int i = 0;i < n;i++)
        {
            int j = ord[i];

            if (after[j].p < 0 || after[j].p > l) printf("Fell off
");
            else if (after[j].sta == -1) printf("%d %s
",after[j].p,"L");
            else if (after[j].sta == 1) printf("%d %s
",after[j].p,"R");
            else printf("%d %s
",after[j].p,"Turning");
        }

        printf("
");
    }

    return 0;
}