题意
请参考LRJ白书第一章例题5
思路
两个蚂蚁相遇会马上调换方向，从视觉上看其实相当于擦身而过（虽然两只蚂蚁的身份并没有交换）。就像在物理中，两个质量相等的小球发生完全弹性碰撞，交换速度。这里是本题第一个思路点。
无论在任何时候，第i只蚂蚁永远是第i只蚂蚁，因为上面也说了，只是视觉上的擦身，实际上蚂蚁又各自回去了。这是第二个思路点。在这个地方还有一个问题，那就是可能会以为仅仅是位置关系保持原来的顺序，其实方向关系也是保持原来的顺序的，这样就可以解决蚂蚁的最终状态的判定问题。
这样我们就有了解法：首先利用擦身而过的想法，求出最终所有蚂蚁的分布。然后利用标号守恒的想法，把终止状态和起始状态对应。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; struct Ant{ int pos; int dir;//1:R -1:L 0:turing int id; bool operator < (const Ant &b) const{ return pos < b.pos; } }; bool cmp(const Ant &a, const Ant &b){ return a.id < b.id; } vector<Ant> all; int loc[10005]; int main(){ int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++){ int L,T,n; scanf(" %d %d %d",&L,&T,&n); Ant tmp; all.clear(); all.resize(n); for(int i = 0; i < n; i++){ tmp.id = i; scanf(" %d",&tmp.pos); char dir; scanf(" %c",&dir); if(dir == 'L'){ tmp.dir = -1; }else{ tmp.dir = 1; } all[i] = tmp; } sort(all.begin(),all.end()); for(int i = 0; i < n; i++){ loc[all[i].id] = i; all[i].pos += all[i].dir * T; } sort(all.begin(),all.end()); for(int i = 0; i < all.size(); i++){ if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){ all[i].dir = 0; } } //sort(all.begin(),all.end(),cmp); printf("Case #%d:\n",d); for(int i = 0; i < all.size(); i++){ if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){ puts("Fell off"); }else{ printf("%d ",all[loc[i]].pos); if(all[loc[i]].dir == 1){ puts("R"); }else if(all[loc[i]].dir == -1){ puts("L"); }else{ puts("Turning"); } } } puts(""); } return 0; } |
