P1007 独木桥

题目背景

战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 1 个人通过。假如有 2 个人相向而行在桥上相遇，那么他们 2 个人将无法绕过对方，只能有 1 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。

题目描述

突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 L，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1，但一个士兵某一时刻来到了坐标为 0 或 L+1 的位置，他就离开了独木桥。

每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。

由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

输入格式

第一行共一个整数 L，表示独木桥的长度。桥上的坐标为 1,2,⋯ ,L1。

第二行共一个整数 N，表示初始时留在桥上的士兵数目。

第三行共有 N 个整数，分别表示每个士兵的初始坐标。

输出格式

共一行，输出 2 个整数，分别表示部队撤离独木桥的最小时间和最大时间。2 个整数由一个空格符分开。

输入输出样例

输入 #1复制

4
2
1 3

输出 #1复制

2 4

说明/提示

对于 100% 的数据，满足初始时，没有两个士兵同在一个坐标，1≤L≤5×10的立方，0≤N≤5×10的立方，且数据保证 N≤L。

解题思路

1. 读取输入：首先读取独木桥的长度 L 和士兵的数量 N，然后读取每个士兵的初始坐标。
2. 特殊情况处理：如果士兵数量为0，则直接输出"0 0"，因为没有士兵需要撤离。
3. 计算士兵到两端的最短距离：对于每个士兵，计算他们到独木桥左端（坐标为0）和右端（坐标为L+1）的最短距离。由于士兵只能朝一个方向走，直到桥的边缘才离开，我们需要考虑士兵是向左走还是向右走能更快地离开桥。这里，我们通过比较士兵当前位置到两端的距离来决定士兵的“等效”初始位置（即如果向右走更快，则等效位置为其当前位置；如果向左走更快，则等效位置为L+1-当前位置）。
4. 排序等效位置：将所有士兵的等效位置进行排序，这样我们就能知道最后一个士兵离开桥所需的最短时间（即最后一个等效位置）。
5. 计算最大时间：我们需要找到士兵中到达桥的最远端（无论是左端还是右端）的最大距离。这是因为有些士兵可能需要走到桥的最远端再返回，或者一直走到桥的另一端才离开，这会决定所有士兵撤离所需的最大时间。
6. 输出结果：根据计算出的最小时间和最大时间输出结果。

示例代码

#include<bits/stdc++.h>  
using namespace std;  
  
int main() {  
    int l, n; // 独木桥的长度和士兵的数量  
    cin >> l >> n;  
    if (n == 0) {  
        cout << "0 0" << endl; // 如果没有士兵，则输出0 0  
        return 0;  
    }  
      
    int a[5005]; // 存储每个士兵的初始坐标  
    int b[10010]; // 存储士兵的等效初始位置（到桥两端的最短距离）  
      
    for (int i = 1; i <= n; i++) {  
        cin >> a[i];  
    }  
      
    // 计算每个士兵的等效初始位置  
    for (int i = 1; i <= n; i++) {  
        if (a[i] <= (l + 1 - a[i])) { // 如果向右走更快或一样快  
            b[i] = a[i];  
        } else { // 如果向左走更快  
            b[i] = l + 1 - a[i];  
        }  
    }  
      
    sort(b + 1, b + n + 1); // 对等效位置进行排序  
      
    int maxr = -1, maxl = -1; // 分别记录士兵到桥左右两端的最大距离  
    for (int i = 1; i <= n; i++) {  
        if (a[i] > maxr) {  
            maxr = a[i]; // 更新到右端的最大距离  
        }  
        if (l + 1 - a[i] > maxl) {  
            maxl = l + 1 - a[i]; // 更新到左端的最大距离  
        }  
    }  
      
    // 输出最小时间和最大时间  
    // 最小时间为最后一个士兵的等效位置，因为所有士兵都会同时开始撤离  
    // 最大时间为士兵到桥两端的最大距离中的较大者  
    if (maxr > maxl) {  
        cout << b[n] << " " << maxr << endl;  
    } else {  
        cout << b[n] << " " << maxl << endl;  
    }  
      
    return 0;  
}