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（复杂问题简单化）

原题传送门

描述

思路

代码

最新文章

热门文章