10881

Question

https://uva.onlinejudge.org/external/108/10881.pdf

Evolution

思路

1. 在图上演示后,可以发现,当两只蚂蚁发生碰撞后,两只蚂蚁将会沿着对方的路线走,也就是说,如果不管它们的身份,那么这两只蚂蚁等同于没有碰撞.因此,我们能够获得T秒后蚂蚁应该存在的位置.
2. 由于蚂蚁碰到障碍物(蚂蚁)就会反弹,很明显木棒上的蚂蚁的相对位置是不变的,因此,我们可以记录输入时蚂蚁初始时的相对位置,输出时参照这一顺序输出.

Need to be awared

蚂蚁可以站在木棒的起点,也即position=0和position=l的时候蚂蚁都没有掉落

Code

#include<cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 10004
int ind[MAXN];
struct Ant{
    int pos;
    int ind;
    int dir;
}a[MAXN];

bool cmp(Ant a1,Ant a2){
    if(a1.pos!=a2.pos)return a1.pos < a2.pos;
    return a2.dir > a1.dir;
}
bool cmpind(Ant a1,Ant a2){
    return a1.ind < a2.ind;
}

int main(){

    //freopen("out.txt", "w", stdout);
    int T;
    scanf("%d",&T);
    for(int ti = 1;ti <= T;ti++){
        int l,t,n;
        scanf("%d%d%d",&l,&t,&n);
        for(int i = 0;i < n;i++){
            char op[2];
            scanf("%d%s",&(a[i].pos),op);
            if(op[0]=='L'){
                a[i].dir = -1;
            }else{
                a[i].dir = 1;
            }
            a[i].ind = i;
        }
        sort(a,a+n,cmp);
        for(int i = 0;i < n;i++){
            ind[i] = a[i].ind;
        }
        for(int i = 0;i < n;i++){
            a[i].pos = a[i].pos + a[i].dir * t;

        }
        sort(a,a+n,cmp);
        for(int i = 0;i < n;i++){
            a[i].ind = ind[i];
            if((i > 0 && a[i].pos == a[i - 1].pos) || (i < n - 1&& a[i].pos == a[i+1].pos)){
                a[i].dir = 0;
            }

        }
        sort(a,a+n,cmpind);
        cout<<"Case #"<<ti<<":"<<endl;
        for(int i = 0;i < n;i++){

            if(a[i].pos < 0 ||a[i].pos > l){\The ant can stand on where pos = 0
                cout<<("Fell off")<<endl;
            }else {
                cout<<a[i].pos<<" "<<(a[i].dir==1?"R":(a[i].dir == 0?"Turning":"L"))<<endl;
            }
        }
        cout<<endl;
    }
    return 0;
}