首页 > 代码库 > (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(蚂蚁)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。