UVA.10881 Piotr's Ants (思维题)

UVA.10881 Piotr’s Ants (思维题)

题意分析

有一根长度为L cm的木棍，上有n只蚂蚁，蚂蚁要么向左爬，要么向右，速度均为1cm/s，若2只蚂蚁相撞，则蚂蚁同时调头。求解第T秒时这n只蚂蚁的状态。

若此时相撞 输出：Turning

若此时已经掉下木棍 输出：Fell off

且要按照输入时的顺序输出各个蚂蚁的状态

此题难点有2个：

1.其实相撞可以理解为交叉走过(因为速度相同)。

2.蚂蚁的相对位置保持不变。

想明白了这两点，难点就转换成了：

1.如何确定蚂蚁的位置；

2.如何处理好蚂蚁的状态。

解决方法如下：

1.首先要按照输入的顺序，给蚂蚁编上号，即ini；

2.给这n只蚂蚁按照从左向右的顺序(即pos升序)排序，并且将其ini写入loca数组。（可以理解为ini是每个蚂蚁的ID，由ini来确认每个蚂蚁的身份)。

3.模拟每只蚂蚁的移动。(利用相撞即交叉走过的原则)。

4.按照移动完的顺序，接着依照pos升序排序。

5.按照loca数组，依次改写从左向右每只蚂蚁的ini(利用的相对位置不变的原则)。

6.按照题目要求输出即可。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 10005

using namespace std;

struct ant{

    int pos,dir,ord,ini;

}a[nmax];

int loca[nmax];

bool cmp(ant x, ant y)

{

    return x.pos<y.pos;

}

bool cmp1(ant x, ant y)

{

    return x.ini<y.ini;

}

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int cas = 0;

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

    int N;

    scanf("%d",&N);

    while(N--){

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

        memset(a,0,sizeof(a));

        memset(loca,0,sizeof(loca));

        int L,T,n;

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

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

            int p;char t;

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

            a[i].pos = p;

            a[i].dir = (t == 'L'?-1:1);

            a[i].ini = i;

        }

        sort(a,a+n,cmp);

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

            loca[i] = a[i].ini;

            a[i].pos = a[i].pos + a[i].dir * T;

        }

        sort(a,a+n,cmp);

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

            a[i].ini = loca[i];

        }

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

            if(a[i].pos == a[i+1].pos) a[i].dir =a[i+1].dir = 0;

        sort(a,a+n,cmp1);

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

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

            else{

                printf("%d %s\n",a[i].pos,arr[a[i].dir+1]);

            }

        }

        printf("\n");

    }

    return 0;

}