题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1822
题目意思:有一条 L 厘米长的杆,上面有 n 只蚂蚁,给出每只蚂蚁的朝向以及离杆上最左端的距离,问 T 秒之后每只蚂蚁到达的位置,如果 T 秒后某个位置有多只蚂蚁同时到达,那么这堆蚂蚁处于的位置 + Turning,如果超过这条杆的长度,输出Fell off,其余情况是:蚂蚁位置+朝向
突发奇想,想做下这题,学习了 lrj 写法。
他的before 和 after 处理,使得蚂蚁在杆子上依次从左到右处理,而且这样做的好处是,不需要对当前的蚂蚁T秒后的位置与已经处理的蚂蚁作比较(检查是否有Turning 情况),大大节省了时间,否则有可能是10000 × 10000 呢~~~order 数组则记下原来最开始时蚂蚁的编号,是为了输出按回原输入啦。
好简洁,好好向他学习^_^
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 10000 + 5; 7 8 struct Ant 9 {10 int id; // 蚂蚁编号11 int p; // 蚂蚁位置12 int d; // 蚂蚁朝向 左: -1 转向:0 右:113 bool operator < (const Ant& a) const14 {15 return p < a.p;16 }17 }before[maxn], after[maxn];18 19 int order[maxn];20 char dirname[][10] = { "L", "Turning", "R"};21 22 int main()23 {24 int N, L, T, n;25 while (scanf("%d", &N) != EOF)26 {27 for (int cas = 1; cas <= N; cas++)28 {29 scanf("%d%d%d", &L, &T, &n);30 int dir;31 char pos;32 for (int i = 0; i < n; i++)33 {34 cin >> dir >> pos;35 int d = (pos == 'R' ? 1 : -1);36 before[i] = (Ant){i, dir, d};37 after[i] = (Ant){ 0, dir+d*T, d};38 }39 sort(before, before+n);40 for (int i = 0; i < n; i++)41 order[before[i].id] = i;42 sort(after, after+n);43 for (int i = 0; i < n-1; i++)44 {45 if (after[i].p == after[i+1].p)46 after[i].d = after[i+1].d = 0; // 碰撞47 }48 printf("Case #%d:\n", cas);49 for (int i = 0; i < n; i++)50 {51 int a = order[i];52 if (after[a].p < 0 || after[a].p > L)53 printf("Fell off\n");54 else55 printf("%d %s\n", after[a].p, dirname[after[a].d+1]); // +1是因为数组下标没有-156 }57 puts("");58 }59 }60 return 0;61 }