UVA.10881 Piotr’s Ants (思维题)
题意分析
有一根长度为L cm的木棍，上有n只蚂蚁，蚂蚁要么向左爬，要么向右，速度均为1cm/s，若2只蚂蚁相撞，则蚂蚁同时调头。求解第T秒时这n只蚂蚁的状态。
若此时相撞 输出：Turning
若此时已经掉下木棍 输出：Fell off
且要按照输入时的顺序输出各个蚂蚁的状态
此题难点有2个：
1.其实相撞可以理解为交叉走过(因为速度相同)。
2.蚂蚁的相对位置保持不变。
想明白了这两点，难点就转换成了：
1.如何确定蚂蚁的位置；
2.如何处理好蚂蚁的状态。
解决方法如下：
1.首先要按照输入的顺序，给蚂蚁编上号，即ini；
2.给这n只蚂蚁按照从左向右的顺序(即pos升序)排序，并且将其ini写入loca数组。（可以理解为ini是每个蚂蚁的ID，由ini来确认每个蚂蚁的身份)。
3.模拟每只蚂蚁的移动。(利用相撞即交叉走过的原则)。
4.按照移动完的顺序，接着依照pos升序排序。
5.按照loca数组，依次改写从左向右每只蚂蚁的ini(利用的相对位置不变的原则)。
6.按照题目要求输出即可。
代码总览
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define nmax 10005
using namespace std;
struct ant{
int pos,dir,ord,ini;
}a[nmax];
int loca[nmax];
bool cmp(ant x, ant y)
{
return x.pos<y.pos;
}
bool cmp1(ant x, ant y)
{
return x.ini<y.ini;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int cas = 0;
const char *arr [] ={"L","Turning","R"};
int N;
scanf("%d",&N);
while(N--){
printf("Case #%d:\n",++cas);
memset(a,0,sizeof(a));
memset(loca,0,sizeof(loca));
int L,T,n;
scanf("%d%d%d",&L,&T,&n);
for(int i = 0; i<n; ++i){
int p;char t;
scanf("%d %c",&p,&t);
a[i].pos = p;
a[i].dir = (t == 'L'?-1:1);
a[i].ini = i;
}
sort(a,a+n,cmp);
for(int i = 0; i<n;++i){
loca[i] = a[i].ini;
a[i].pos = a[i].pos + a[i].dir * T;
}
sort(a,a+n,cmp);
for(int i = 0;i<n;++i){
a[i].ini = loca[i];
}
for(int i = 0; i<n-1;++i)
if(a[i].pos == a[i+1].pos) a[i].dir =a[i+1].dir = 0;
sort(a,a+n,cmp1);
for(int i = 0;i<n;++i){
if(a[i].pos<0 || a[i].pos>L) printf("Fell off\n");
else{
printf("%d %s\n",a[i].pos,arr[a[i].dir+1]);
}
}
printf("\n");
}
return 0;
}