pku 1852,题目大意是:
有一队蚂蚁n只在一条线上,蚂蚁以1cm/s的速度沿着线走,线长已知,但每只蚂蚁行走的方向不知(两个方向都可以走)。另外蚂蚁一走到线末端就掉下去,而两只蚂蚁一旦碰头就各自掉头向反方向走去。问所有蚂蚁掉下去的最早时刻跟最迟时刻。
此题粗看似乎很难。两只蚂蚁碰头就各自掉头这个条件其实是干扰项,因为可以看作两个方向向量交换,速度跟方向其实都不变(不管是哪只蚂蚁往哪个方向)。
这样题目就简单了,可以把n只蚂蚁看作是在独立的n条线上行走。
最早的时间就是每只蚂蚁都往最近的一端走,最后一只蚂蚁掉下去的时刻就是最早时刻;而最迟时间就是每只蚂蚁都往最远端走,最后一只蚂蚁掉下去的时刻也就是最迟时刻。
代码如下:
1
#include <iostream>
2
3
using namespace std;
4
5
long min(long a,long b)
6

{
7
return a>b?b:a;
8
}
9
10
long max(long a,long b)
11

{
12
return a>b?a:b;
13
}
14
15
int 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
}