首页 > 代码库 > uva 10881 Piotr's Ants 解题报告
uva 10881 Piotr's Ants 解题报告
题目链接：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 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 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 }
uva 10881 Piotr's Ants 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。