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
- epicrado. UVa – 10714 – Ants. f0rth3r3c0rd UVa solutions! And more !!. Posted May 21, 2013 by epicrado in Greedy
- [日]秋叶拓哉, 岩田阳一, 北川宜稔 著. 巫泽俊, 庄俊元, 李津羽 译. 《挑战程序设计竞赛（第2版）》. 人民邮电出版社. ISBN 978-7-115-32010-0