UVa 10881 Piotr's Ants (等价变换)

时间:2022-09-05 19:17:24

题意:一个长度为L的木棍上有n个蚂蚁,每只蚂蚁要么向左,要么向右,速度为1,当两只蚂蚁相撞时,

它们同时掉头。给定每只蚂蚁初始位置和朝向,问T秒后,每只蚂蚁的状态。

析:刚看到这个题时,一点思路也没有,怎么做啊,难道又要模拟么,一想,模拟。。。天呐,好麻烦!

最终还是看了一下题解。真是很巧妙哪。

首先是当两个蚂蚁相撞时,转向和不转向是看不出来的。也就是说掉头等价于对穿而过。也就是说,

如果把蚂蚁看成是没有区别的小点,那么只要独立算每只蚂蚁的位置即可。虽然是这么说,但是,

对每只蚂蚁却不是这样,但是我们只要搞清楚了谁是谁了,就能搞定。

最重要的一点是,每只蚂蚁的相对顺序是不会变的,这才是核心。因此把所有目标位置从小到大排序,

刚从左到右的每个位置都是和初始状态下一样的。由于输入顺序不一定是按从左到右,所以需要预处理一下。

代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std;
typedef long long LL;
const int maxn = 10000 + 10;
struct node{
int id, p, d;
node(int i = 0, int pp = 0, int dd = 0) : id(i), p(pp), d(dd) { }
bool operator < (const node &q) const {
return p < q.p;
}
};
node a[maxn], b[maxn];
int o[maxn]; int main(){
int t, T, l, n, cases = 0; cin >> T;
while(T--){
scanf("%d %d %d", &l, &t, &n);
for(int i = 0; i < n; ++i){
char ch;
scanf("%d %c", &a[i].p, &ch);
a[i].id = i;
a[i].d = (ch == 'L' ? -1 : 1);//-1表示向左,1表示向右
b[i] = node(0, a[i].p + t*a[i].d, a[i].d); //id是未知的
} sort(a, a+n);//按照从左到右的顺序排列
for(int i = 0; i < n; ++i)
o[a[i].id] = i;//确定顺序数组
sort(b, b+n);//计算最后状态 printf("Case #%d:\n", ++cases);
for(int i = 0; i < n; ++i){
int d = o[i];//对应顺序
if(b[d].p < 0 || b[d].p > l) printf("Fell off\n");
else if(b[d].p == b[d+1].p || b[d].p == b[d-1].p) printf("%d Turning\n", b[d].p);
else printf("%d %c\n", b[d].p, b[d].d == 1 ? 'R' : 'L');
}
printf("\n");
}
return 0;
}