首页 > 代码库 > (POJ)1852 --Ants(蚂蚁)

(POJ)1852 --Ants(蚂蚁)

描述
蚂蚁的军队在长度lcm的水平杆上行走,每个具有1cm / s的恒定速度。当一个行走的蚂蚁到达杆的一端,它立即掉落。当两只蚂蚁相遇时,他们返回,开始朝着相反的方向走。我们知道蚂蚁在杆子上的原始位置,不幸的是,我们不知道蚂蚁行走的方向。你的任务是计算所有蚂蚁脱离杆子所需的最短和最长的可能时间。


输入
第一行输入包含一个整数,给出情况数。每种情况的数据以两个整数开始:杆子的长度(以cm为单位),n是驻杆子上的蚂蚁的数量。这两个数字后跟随n个整数,给出在杆上的每个蚂蚁的位置作为从杆的左端测量的距离,没有特定顺序。所有输入整数不大于1000000,它们由空格分隔。


输出
对于每种情况的输入,输出由一个空格分隔的两个数字。第一个数字是所有蚂蚁离开杆子的最早可能的时间(如果他们的步行的方向被适当地选择),第二个数字是最长可能的这样的时间。


样例输入
2
10 3
2 6 7
214 7
11 12 7 13 176 23 191


样例输出
4 8
38 207

 

 

这个题目可以忽略蚂蚁的碰撞, 将每个蚂蚁的运动最短时间和最长时间都求出来,分别取里面的最大值。

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int t,x,i;
10     scanf("%d",&t);
11     while(t--)
12     {
13         int l,n,max_time=0,min_time=0;
14         scanf("%d %d",&l,&n);
15         for(i=1;i<=n;i++)
16         {
17             scanf("%d",&x);
18             max_time=max(max_time,max(x,l-x));
19             min_time=max(min_time,min(x,l-x));
20         }
21         printf("%d %d\n",min_time,max_time);
22     }
23     return 0;
24 }
答案

 

(POJ)1852 --Ants(蚂蚁)