cogs 1456. [UVa 10881,Piotr's Ants]蚂蚁

2023-08-05 22:39:28

1456. [UVa 10881,Piotr's Ants]蚂蚁

★ 输入文件：Ants.in 输出文件：Ants.out 简单对比
时间限制：1 s 内存限制：128 MB

【题目描述】

一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么往左爬要么往右爬，速度为1cm/s。当两只蚂蚁相遇时，二者同时掉头(掉头时间忽略不计)。给出每只蚂蚁的初始位置和朝向，计算T秒之后蚂蚁的位置。

【输入格式】

输入第一行为数据组数。每组第一行为三个整数L,T,n(n≤10 000)；以下n行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距左端的距离(单位：厘米)，字母表示初始朝向(L向左，R向右)。

【输出格式】

对于每组数据，输出n(Case #n:)，按输入顺序输出每只蚂蚁的位置和朝向(Turning表示正在碰撞)。在T秒之前已经掉落的蚂蚁(正好爬到边缘不算)输出Fell off

【样例输入】

2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R

【样例输出】

Case #1:
2 Turning
6 R
2 Turning
Fell off
Case #2:
3 L
6 R
10 R

【来源】

UVa 10881,Piotr's Ants

思路：

　　假设你在远处观察这些蚂蚁的运动，会看到什么？一群密密麻麻的小黑点在移动。由于黑点太小，所以当蚂蚁一碰撞而掉头时，看上去和两个点”对穿而过“没有什么区别。换句话说，如果把蚂蚁看做是没有区别的小点，那么只需要计算出每只蚂蚁在T时刻的位置即可。比如，有3只蚂蚁，蚂蚁1=（1，R），蚂蚁2=（3，L），蚂蚁3=（4，L），则两秒之后，三只蚂蚁分别为（3，R），（1，L）和（2，L）。

　　注意，虽然从整体上讲，”掉头“等价于”对穿而过“，但对于每只蚂蚁而言，并不是这样。蚂蚁1的初始状态为（1，R），因此一定有一只蚂蚁在两秒钟之后处于（3，R）的状态，但这只蚂蚁却不一定是蚂蚁1.换句话说，我们需要搞清楚目标状态中的”谁是谁“。

　　可以想象一下，所有蚂蚁的相对顺序是保持不变的。然后这个问题就很好解决了。

这是代码：

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 10001

using namespace std;

map<int,int>vis;

int T;

int len,t,n,num;

struct nond{

    int pos,turn,id;

}v[MAXN],vv[MAXN];

int cmp(nond a,nond b){

    return a.pos<b.pos;

}

int cmp1(nond a,nond b){

    return a.id<b.id;

}

int main(){

    freopen("Ants.in","r",stdin);

    freopen("Ants.out","w",stdout);

    scanf("%d",&T);

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

        vis.clear();

        memset(v,,sizeof(v));

        memset(vv,,sizeof(vv));

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

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

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

            char c;

            scanf("%d %c",&v[i].pos,&c);

            if(c=='R')    v[i].turn=;

            else v[i].turn=-;

            v[i].id=i;vv[i]=v[i];

        }

        sort(v+,v++n,cmp);

        sort(vv+,vv++n,cmp);

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

            if(vv[i].turn==-)    vv[i].pos-=t;

            else if(vv[i].turn==)    vv[i].pos+=t;

            if(vv[i].pos>len||vv[i].pos<)    vv[i].turn=;

            else vis[vv[i].pos]++;

        }

        sort(vv+,vv++n,cmp);

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

            v[i].pos=vv[i].pos;

            v[i].turn=vv[i].turn;

        }

        sort(v+,v++n,cmp1);

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

            if(v[i].turn==)    cout<<"Fell off"<<endl;

            else if(vis[v[i].pos]!=)    cout<<v[i].pos<<" "<<"Turning"<<endl;

            else if(v[i].turn==)    cout<<v[i].pos<<" "<<"R"<<endl;

            else cout<<v[i].pos<<" "<<"L"<<endl;

        }

    }

}

码农公寓