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

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;

}

巴特西

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

1.POJ 1852 Ants

2.UVA 10881 - Piotr's Ants

最新文章

热门文章