pku 1852，題目大意是：
有一隊(duì)螞蟻n只在一條線上，螞蟻以1cm/s的速度沿著線走，線長(zhǎng)已知，但每只螞蟻行走的方向不知（兩個(gè)方向都可以走）。另外螞蟻一走到線末端就掉下去，而兩只螞蟻一旦碰頭就各自掉頭向反方向走去。問(wèn)所有螞蟻掉下去的最早時(shí)刻跟最遲時(shí)刻。
此題粗看似乎很難。兩只螞蟻碰頭就各自掉頭這個(gè)條件其實(shí)是干擾項(xiàng)，因?yàn)榭梢钥醋鲀蓚€(gè)方向向量交換，速度跟方向其實(shí)都不變（不管是哪只螞蟻往哪個(gè)方向）。
這樣題目就簡(jiǎn)單了，可以把n只螞蟻看作是在獨(dú)立的n條線上行走。
最早的時(shí)間就是每只螞蟻都往最近的一端走，最后一只螞蟻掉下去的時(shí)刻就是最早時(shí)刻；而最遲時(shí)間就是每只螞蟻都往最遠(yuǎn)端走，最后一只螞蟻掉下去的時(shí)刻也就是最遲時(shí)刻。
代碼如下：
1
#include <iostream>
2
3using namespace std;
4
5long min(long a,long b)
6
{
7
return a>b?b:a;
8
}
9
10long max(long a,long b)
11{
12 return a>b?a:b;
13}
14
15int main()
16{
17 long maxi,mini;
18 long t;
19 scanf("%ld",&t);
20 while(t--)
21
{
22 long l,n,x;
23 scanf("%ld%ld",&l,&n);
24 scanf("%ld",&x);
25 maxi=max(x,l-x);
26 mini=min(x,l-x);
27 for(long i=0;i<n-1;i++)
28 {
29 scanf("%ld",&x);
30 long tmp=max(x,l-x);
31 maxi=maxi<tmp?tmp:maxi;
32 tmp=min(x,l-x);
33 mini=mini<tmp?tmp:mini;
34
}
35 printf("%ld %ld\n",mini,maxi);
36 }
37 return 1;
38}