两题很有趣挺经典的蚂蚁问题。
1.n只蚂蚁以1cm/s的速度在长为L的竿上爬行，当蚂蚁爬到竿子的端点就会掉落。当两只蚂蚁相撞时，只能各自反向爬回去。对于每只蚂蚁，给出距离左端的距离xi，但不知道它的朝向，求所有蚂蚁落下竿子所需要的时间的最大值和最小值。
2.问题1的升级版：把问题1改为已知每只蚂蚁的左端距离和它的朝向，要求按输入顺序输出 t 秒后每只蚂蚁的位置和状态（掉出去，转向中，或者蚂蚁的朝向）。
1.POJ 1852 Ants
http://poj.org/problem?id=1852
思路：
很水的一题，因为以前做过问题2.so......
因为蚂蚁碰撞会反向，故我们可以直接看成是蚂蚁直接穿过去。
也就是说，这道题求解只需要独立的计算出每只蚂蚁到端点的时间即可。
最小时间只需要沿着靠近的一端走，最大时间则最远的一端。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,L,n;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int min_ans=0,max_ans=0;
scanf("%d%d",&L,&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
min_ans=max(min_ans,min(L-a,a)); //选择小的一段走
max_ans=max(max_ans,max(L-a,a)); //选择长的一段走
//因为是计算总的时间故应取最大值。
}
printf("%d %d\n",min_ans,max_ans);
}
return 0;
}
2.UVA 10881 - Piotr's Ants
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1822
思路：
《算法竞赛入门经典-训练指南》上的题。
半年前被虐个半死，今天是我把他虐个半死。
和问题1的差别在于要求出位置。
那么，同样的，每只蚂蚁碰撞后反向，所以每只蚂蚁的相对顺序不变。（突然想起“不撞南墙不回头”。。。。。。。）
所以我们根据一开始排个序，记录此时所有蚂蚁的序号，然后计算ts后的位置。（计算我们直接加上距离，你想，0s有一只向右的位置在x的，那么ts后一只向右的位置在x+t的，不管是不是一开始向右的那只还是和他碰撞的，我们可以看为穿过去）
接下来再次根据位置排序，将序号进行“还原”，即对应上原来在竿上的位置。
最后根据序号按顺序输出即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10000+10;
int L,t,n;
int order[MAXN];
char string[][10]={"L","R","Turning"};
struct data
{
int id; //输入的顺序
int x; //位置
int dir; //方向 0 左 1右 2碰撞
bool operator<(const data &y)const{
return x<y.x;
}
}a[MAXN];
bool cmp(const data& x,const data&y)
{
return x.id<y.id;
}
int main()
{
int T,kase=1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&L,&t,&n);
for(int i=0;i<n;i++)
{
char dir;
scanf("%d %c",&a[i].x,&dir);
if(dir=='L') a[i].dir=0;
else a[i].dir=1;
a[i].id=i;
}
//每只蚂蚁的相对次序是不变的，原来在左边的之后还会在左边。
sort(a,a+n); for(int i=0;i<n;i++)
{
order[i]=a[i].id;
if(a[i].dir==0)
a[i].x-=t;
else
a[i].x+=t;
}
//再次排序即可由最后的位置确定对应的输入序号（相对位置不变）
sort(a,a+n);
for(int i=0;i<n-1;i++)
{
a[i].id=order[i];
if(a[i].x==a[i+1].x)
a[i+1].dir=a[i].dir=2;
}
a[n-1].id=order[n-1]; sort(a,a+n,cmp); //根据输入的顺序排序
printf("Case #%d:\n",kase++);
for(int i=0;i<n;i++)
{
if(a[i].x<0||a[i].x>L) //掉出去了
printf("Fell off\n");
else
printf("%d %s\n",a[i].x,string[a[i].dir]); //根据方向输出状态。
}
printf("\n");
}
return 0;
}