首页 > 代码库 > UVa 10881 蚂蚁
UVa 10881 蚂蚁
https://vjudge.net/problem/UVA-10881
题意：
一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。
思路：
首先，如果不考虑掉头的话，蚂蚁相遇时就是对穿而过，如果考虑掉头，局势是不会发生改变的，就是蚂蚁的位置不同。
比如蚂蚁1（2，R），蚂蚁2（4，L），经过3秒后，如果不考虑掉头，那么蚂蚁1（5，R），蚂蚁2（1，L）。如果考虑掉头，则蚂蚁1（1 , L），蚂蚁2（5 , R）。也就是说不管怎样，总有蚂蚁会在（1，L），也总有蚂蚁会在（5，R），所以一开始我们可以不用考虑掉头来计算出所有蚂蚁最后的状态，我们需要确定的就是哪只蚂蚁处于这个状态。
接下来的一点很重要，因为蚂蚁相撞后会掉头，所以蚂蚁的相对顺序是不会变的，也就是说最左边的蚂蚁肯定一直在最左边，从左往右第1只 蚂蚁也肯定一直处于第1只...这个想一下就可以理解了。
既然这样，最后只需要按照坐标排序然后和蚂蚁匹配就可以了。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 int l, t, n; 6 7 const int maxn = 10000 + 5; 8 9 struct node10 {11 int id;12 int p;13 int d; //方向，-1表示往左，0表示碰撞，1表示往右14 bool operator <(const node& rhs) const15 {16 return p < rhs.p;17 }18 }before[maxn],after[maxn];19 20 int order[maxn];21 22 char dir[][10] = { "L", "Turning", "R" };23 24 int main()25 {26 ios::sync_with_stdio(false);27 //freopen("D:\\txt.txt", "r", stdin);28 int T;29 int p;30 char c;31 int kase = 0;32 cin >> T;33 while (T--)34 {35 cin >> l >> t >> n;36 for (int i=0; i < n; i++)37 {38 cin >> p >> c;39 int d = c == ‘L‘ ? -1 : 1;40 before[i].id = i;41 before[i].p = p;42 before[i].d = d;43 after[i].id = 0;44 after[i].p = t*d + p;45 after[i].d = d;46 }47 sort(before, before + n);48 for (int i = 0; i < n; i++)49 {50 order[before[i].id] = i;51 }52 53 sort(after, after + n);54 for (int i = 0; i < n;i++)55 if (after[i].p == after[i + 1].p)56 after[i].d = after[i + 1].d = 0;57 58 cout << "Case #" << ++kase << ":" << endl;59 for (int i = 0; i < n; i++)60 {61 int num = order[i];62 if (after[num].p<0 || after[num].p>l) cout << "Fell off" << endl;63 else cout << after[num].p << " " << dir[after[num].d + 1] << endl;64 }65 cout << endl;66 }67 }
UVa 10881 蚂蚁
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。