POJ1852 Ants

October 15, 2018
作者:DaleiZhou
出处:http://www.daleizhou.tech/posts/poj1852-ants.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

内容

Status: Release

  今天的题目答案很简单,难的是想到解题思路,让我们一起看POJ1852[1]吧。

Problem

Description

An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.

Input

The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.

Output

For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time. 

Sample Input

2
10 3
2 6 7
214 7
11 12 7 13 176 23 191

Sample Output

4 8
38 207

Analysis

  本题是白书[2]上介绍例题的第二题,因此不会很难。但是一开始拿到题目好像只有暴力搜索这么一个思路。因为只知道每个蚂蚁初始的位置,但是不知道方向,因此枚举尽所有方向的可能,那就是\( 2 \times 2 \times … \times 2 = 2^{n} \),这种指数级的时间复杂度肯定不是我们想要的。

  我们之所以想穷举所有方向的可能,就是因为要考虑蚂蚁相遇的问题,相遇之后立即向相反的方向走,这其中的可能情况想想都头大。我一开始也没想到怎么处理,直接看了白书上答案。

  根据题目的意思是蚂蚁相遇后往相反方向前进,但是这里隐含的意思是我们识别了一个个独立的个体,假如在我们眼里只有蚂蚁,没有是哪一只蚂蚁的区别,那么相遇后的情况就可以看成是下图所示:

  在无视蚂蚁区别的基础上,可以看成相遇后无阻碍的沿着原方向继续前进,可以把蚂蚁单独拿出来看,独立前进没有任何障碍。因此要求的所有蚂蚁掉落最短时间时间,只需要求一个个蚂蚁到竿子尽头最短时间的最大值就好。这么处理之后时间复杂度就降到了O(n)。实际解题过程中,要注意杆子端点的坐标值,下面直接看AC的代码吧。

AC Code

#include<cstdio>
#include<vector>
using namespace std;

int main() {
#ifdef POJ_DEBUG_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int T, L, n;
    while (scanf("%d", &T) != EOF) {
        while (T--) {
            scanf("%d %d", &L, &n);
            vector<int> ants;
            int temp;
            while (n--) {
                scanf("%d", &temp);
                ants.push_back(temp);
            }

            int minT = 0;
            for (int i = 0; i < ants.size(); ++i) {
                minT = max(minT, min(L - ants[i], ants[i]));
            }

            int maxT = 0;
            for (int i = 0; i < ants.size(); ++i) {
                maxT = max(maxT, max(ants[i], L - ants[i]));
            }

            printf("%d %d\n", minT, maxT);
        }
    }

#ifdef POJ_DEBUG_LOCAL
    fclose(stdin);
    fclose(stdout);
#endif
}

References