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;
}
}