首页 > 代码库 > poj_1852_Ants(复杂问题简单化)
poj_1852_Ants(复杂问题简单化)
原题传送门
描述
一群蚂蚁走在长度为l cm的水平细杆上,以1cm/s的匀速。当一只行走的蚂蚁到达杆的一端,它就会掉下去。当两只蚂蚁相遇,它们会掉头像反方向走去。我们知道一只蚂蚁在杆上的初始位置,然而,我们不知道蚂蚁在像哪一个方向走。你的任务是计算所有蚂蚁从杆上掉下所需的最早和最晚的时间。
思路
1.如果每只蚂蚁都向近的那一端走,蚂蚁一定不会相遇,最后一只蚂蚁到达端点所用的时间即为最短时间。
证明:取中点q.根据以上原则,在q左边的蚂蚁会向左爬,在q右边的蚂蚁会像右爬。因此任意两只蚂蚁不会相遇。又由于每只蚂蚁都向较近的的那一端爬,对于每只蚂蚁,爬到端点的时间最短。因此,最后一只到达端点的蚂蚁所用时间即为最短总时间。即t_min=max=(t_min,min(x[i],L-x[i]))
2.对于最大时间,
表面上看,蚂蚁相遇次数越多越好,因为这样蚂蚁就会不断在杆上往返,增加总的时间。那么,有没有一个时间上限呢?
考虑两只蚂蚁相遇的情况,如果把每只蚂蚁看作完全一样毫无差别的,那么,蚂蚁的相遇也可以看作如下图所示的情况:
因此,最大时间是所有蚂蚁到最远端所用时间中最大的那一个时间,及t_max=max(t_max,max(x[i],L-x[i]))
代码
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 5 using namespace std; 6 7 int anti[1000003]; 8 9 int main() 10 { 11 int cas; 12 cin >> cas; 13 while (cas--) 14 { 15 int L, n; 16 cin >> L >> n; 17 18 for (int i = 0; i < n; i++) 19 //cin >> anti[i]; 20 scanf("%d", &anti[i]); 21 22 23 int t_max=0,t_min=0; 24 for (int i = 0; i < n; i++) 25 { 26 t_max = max(t_max,max(anti[i],L - anti[i]) ); 27 t_min = max(t_min,min(anti[i],L - anti[i]) ); 28 } 29 30 cout << t_min << " " << t_max << endl; 31 } 32 return 0; 33 }
poj_1852_Ants(复杂问题简单化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。