欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

uva --- UVA10881蚂蚁

程序员文章站 2024-03-18 23:59:52
...

题意:
     在一个木棍上有只小蚂蚁,他们的移动速度都是1,移动的时候如果和别的蚂蚁碰面,那么碰面的这两只小蚂蚁会马上掉头继续走,给你每只蚂蚁的初始距离木棒左端点的距离和方向,以及木棍长度,问你t时间后每个蚂蚁的状态。

思路:
      比较有意思的题,其实对于这个题目,我们考虑下,如果所有的蚂蚁都没有区别,那么两只蚂蚁相遇是不是相当于"穿过去"了?那么有区别的时候呢?其实也可以考虑是直接穿过去了,只不过蚂蚁的名字一直在变化而已,但无论怎么变,蚂蚁的相对位置不会改变.所以我们可以对初始的蚂蚁的位置进行排序<之前记得存上他们的id>,然后在把最终的位置处理出来,然后在排序,然后在一一对应给赋值回去,至于方向也是跟着最终位置一起赋值回去。

存在问题:1. 理解这种思路,思维决定方法,理解蚂蚁这种穿过处理,理解可以想象木棍无限长。

                  2,这里我使用Oder来记录这种映射,那么错误的是 order[i]=tnode.ord; 正确的是order[tnode.ord]=i; 

                  3, 提交的时候讲 turning错误为turing,WA了,悲催!要细心

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define MAX 10005
typedef struct {
    int pos;
    string idir;
    int ord;
} Node;
Node dat[MAX];
int order[MAX];
bool mycmp(Node a,Node b)
{
    return a.pos<b.pos;
}
int main() {
    bool mycmp(Node a,Node b);
    int t;
    cin>>t;
    int L,T,n;
    int cnt=1;
    Node node;
    int Kcase=0;
    while(Kcase++<t)
    {
        cin>>L>>T>>n;
        int tn1;
        char tc1;
        cnt=0;
        for(int i=0; i<n; i++)
        {
            cin>>tn1>>tc1;
            node.idir=tc1;
            node.ord=cnt++;
            node.pos=tn1;
            dat[i]=node;
        }
        sort(dat,dat+n,mycmp);
        //for(int i=0;i<n;i++) cout<<dat[i].pos<<" ["<<dat[i].ord<<"] "; cout<<endl;
        for(int i=0; i<n; i++)
        {
            Node &tnode=dat[i];
            order[tnode.ord]=i;
            if(tnode.idir=="R")
                tnode.pos+=T;
            else if(tnode.idir=="L")
                tnode.pos-=T;
        }
        sort(dat,dat+n,mycmp);
        //for(int i=0;i<n;i++) cout<<dat[i].pos<<" ["<<dat[i].ord<<"] "; cout<<endl;
        for(int i=0; i<n; i++)
        {
            if(i>0&&dat[i].pos==dat[i-1].pos)
            {
                dat[i].idir="Turning";
                dat[i-1].idir="Turning";
            }
            if(dat[i].pos<0||dat[i].pos>L)
                dat[i].idir="Fell off";
        }
        cout<<"Case #"<<Kcase<<":"<<endl;
        for(int i=0; i<n; i++)
        {
            if(dat[order[i]].idir=="Fell off")
                cout<<dat[order[i]].idir<<endl;
            else
                cout<<dat[order[i]].pos<<" "<<dat[order[i]].idir<<endl;

        }

        cout<<endl;
    }
}