算法入门经典训练指南上的题。
这里有必要讲一下蚂蚁爬杆问题:每只蚂蚁都有一个初始方向,相撞会转向,关键就是相撞的处理,由于速度并不会改变,两只蚂蚁相撞,可以看做,两只蚂蚁穿过对方,继续沿原方向前进,经过t秒,最后蚂蚁的最终位置是固定的,但是对应位置的蚂蚁有可能不再是原来的蚂蚁;现在考虑经过t秒后蚂蚁的位置,假设蚂蚁刚开始以离杆的左端距离升序排序,那么t秒后,他们的位置排序不会改变,举例说明:如果以前有一只蚂蚁排在第二,t秒后它仍然在第二。
AC代码:
#include<cstdio> #include<algorithm> using namespace std; const int maxn=10000+5; struct node{ int num; int pos; char dir; }a[maxn],b[maxn]; bool cmp1(node &p1,node &p2){ return p1.pos<p2.pos; } bool cmp2(node &p1,node &p2){ return p1.num<p2.num; } int main(){ int T,kase=1; scanf("%d",&T); while(T--){ int len,t,n; scanf("%d%d%d",&len,&t,&n); int pos; char dir; for(int i=0;i<n;++i){ scanf("%d %c",&a[i].pos,&a[i].dir); a[i].num=i; b[i].dir=a[i].dir; if(b[i].dir=='L') b[i].pos=a[i].pos-t; else b[i].pos=a[i].pos+t; } sort(b,b+n,cmp1); sort(a,a+n,cmp1); for(int i=0;i<n;++i){ if((i<n-1&&b[i].pos==b[i+1].pos)||(i>0&&b[i].pos==b[i-1].pos)){ a[i].pos=b[i].pos; a[i].dir='r'; } else{ a[i].pos=b[i].pos; a[i].dir=b[i].dir; } } sort(a,a+n,cmp2); printf("Case #%d:\n",kase++); for(int i=0;i<n;++i){ if(a[i].pos<0||a[i].pos>len) printf("Fell off\n"); else if(a[i].dir=='r') printf("%d Turning\n",a[i].pos); else printf("%d %c\n",a[i].pos,a[i].dir); } printf("\n"); } return 0; }
如有不当之处欢迎指出!