Personal nest in the information age

UVa OJ 10714 – Ants

Browse problem

Solution

Thinking

If all the ants are going to the nearest end of the pole, it is easy to find the earliest time needed.

只要所有的蚂蚁都走到杆的最近端,求出所需的最短时间就很简单。

Find the latest time (找出最长时间)

If there are two or more ants, pole can be likened to a relay race field, and the ants are like passing the baton. When the ants meet, they replace each other and walk the rest of the way to the end of the pole. The transfer of the baton here can be understood as the consumption of time. When the end of the pole is reached, the relay ends and the time expires.

如果有两只甚至更多只蚂蚁,可以将杆子比作接力赛赛场,蚂蚁间就像传递接力棒一样,当蚂蚁碰面时,相互代替对方走完剩下的路程直至端点。这里的接力棒的传递可以理解为时间的消耗。到达端点接力结束、时间截至。

Further, we can think that the ants will continue to walk forward when meeting each other , which is equivalent to the ants turning back.. So if you want to find the latest time, just find the maximum distance from the ant to the end of the pole.

进一步我们可以认为蚂蚁碰面什么都没发生和蚂蚁碰面后转向的最终结果是一致的。因此想要求出最长时间,只要求出蚂蚁到杆子端点的最大距离即可。

C++ code

#include<cstdio>
using namespace std;
int main(void){
	int n;
	scanf("%d",&n);
	while(n--){
		int len,ants,min=0,max=0;
		scanf("%d %d",&len,&ants);
		while(ants--){
			int ant,min_t,max_t;
			scanf("%d",&ant);
			if(ant< len-ant){
				min_t=ant;
				max_t=len-ant;
			}else{
				min_t=len-ant;
				max_t=ant;
			}
			if(min<min_t)
				min=min_t;
			if(max<max_t)
				max=max_t;
		}
		printf("%d %d\n",min,max);
	}
	return 0;
}

Bibliography

Leave a comment

Your email address will not be published. Required fields are marked *