POJ 1852 Ants || UVA 10881 - Piotr's Ants 经典的蚂蚁问题

两题很有趣挺经典的蚂蚁问题。

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;
}
上一篇:思维题 UVA 10881 Piotr's Ants


下一篇:Uva 10881 Piotr’s Ants 蚂蚁