1623 - 坠落的蚂蚁
时间限制 : 1 秒
内存限制 : 32 MB
一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘（0或100厘米处）则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即1，2，3，…99厘米），有且只有一只蚂蚁A速度为0，其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁A从此时刻到坠落所需要的时间。
题目输入
第一行包含一个整数表示蚂蚁的个数N（2<=N<=99），之后共有N行，每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数P（1<=P<=99），第二个数字表示初始方向,-1表示向左，1表示向右，0表示静止。
题目输出
蚂蚁A从开始到坠落的时间。若不会坠落，输出“Cannot fall!”
输入/输出样例
输入格式
2 44 0 41 1 2 13 0 63 1 4 56 0 64 -1 85 -1 47 1
输出格式
59 Cannot fall! 85
C语言解答
struct number {double address; int direction; }num[100]; int main(int argc, char* argv[]) {int n,i,j,mb,count,time,k,kj,bh[3],tem; double i1; while(~scanf("%d",&n)) { time=0;k=0;kj=0; for(i=0;i<n;i++) { scanf("%lf%d",&num[i].address,&num[i].direction); if(num[i].direction==0)mb=i; } while(1) { if(k==1)break; for(i1=0;i1<=100;i1=i1+0.5) { count=0; for(j=0;j<n;j++) if(i1==num[j].address){bh[count]=j;count++;} if(count==2){ tem=num[bh[0]].direction;num[bh[0]].direction=num[bh[1]].direction;num[bh[1]].direction=tem;} if(count==3){ if(num[bh[0]].direction==0){ tem=num[bh[1]].direction;num[bh[1]].direction=num[bh[2]].direction;num[bh[2]].direction=tem;} if(num[bh[1]].direction==0){ tem=num[bh[0]].direction;num[bh[0]].direction=num[bh[2]].direction;num[bh[2]].direction=tem;} if(num[bh[2]].direction==0){ tem=num[bh[1]].direction;num[bh[1]].direction=num[bh[0]].direction;num[bh[0]].direction=tem;} } } for(j=0;j<n;j++) { if(num[j].address==0||num[j].address==100) { if(j==mb){printf("%d\n",time/2);k=1;break;} else {kj++;num[j].direction=0;num[j].address=-1; } } num[j].address+=num[j].direction*0.5; } if(n-kj==1){printf("Cannot fall!\n");k=1;} time++; } } return 0; }
C++解答
#include <iostream> #include <algorithm> using namespace std; struct Node { int speed; int position; }ant[110]; void Swap(int a,int b) { int tmp=ant[a].speed; ant[a].speed=ant[b].speed; ant[b].speed=tmp; } bool cmp(Node a,Node b) { return a.position<b.position; } int gao(int N,int goal) { int head=0,tail=N-1; int time=0; while(1) { if(time>210)return -1; time++; for(int i=head;i<=tail;i++) ant[i].position+=ant[i].speed;//每0.5秒移动一次 for(int i=head;i<=tail;i++) if(ant[i].speed==1)//两移动的蚂蚁相撞 { if(i<tail&&ant[i+1].speed==-1&&ant[i+1].position==ant[i].position) Swap(i,i+1); } else if(ant[i].speed==-1) { if(i>head&&ant[i-1].speed==-1&&ant[i-1].position==ant[i].position) Swap(i-1,i); } else if(ant[i].speed==0)//三只蚂蚁相撞 { if(i>head&&i<tail&&ant[i].position==ant[i-1].position&&ant[i].position==ant[i+1].position&&ant[i-1].speed==1&&ant[i+1].speed==-1) Swap(i-1,i+1);//左边的蚂蚁撞上静止的蚂蚁 else if(i>head&&ant[i].position==ant[i-1].position&&ant[i-1].speed==1) Swap(i-1,i);//右边的蚂蚁撞上静止的蚂蚁 else if(i<tail&&ant[i].position==ant[i+1].position&&ant[i+1].speed==-1) Swap(i,i+1); } if(ant[goal].position<=0||ant[goal].position>=200)return time/2; if(ant[head].position<=0)head++; if(ant[tail].position>=200)tail--; } return -1; } int main() { int N; while(cin>>N) { int goal=-1; for(int i=0;i<N;i++) { cin>>ant[i].position>>ant[i].speed; ant[i].position*=2; } sort(ant,ant+N,cmp); for(int i=0;i<N;i++) if(ant[i].speed==0) goal=i; int res=gao(N,goal); if(res==-1) cout<<"Cannot fall!"<<endl; else cout<<res<<endl; } return 0; }