本题是洛谷P1007题，重点是将相撞问题变换视角，看似是相撞，实则是两人各自成为了对方，在替对方完成任务。

独木桥

题目背景

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

题目描述

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

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

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

输入格式

第一行共一个整数，表示独木桥的长度。桥上的坐标为。

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
3

4
2
1 3

样例输出 #1

2 4

提示

对于的数据，满足初始时，没有两个士兵同在一个坐标，，，且数据保证。

题解

1. 问题等价

假设有以下独木桥，士兵1位于1位置，士兵2位于2位置。他们相对而行。

$0----1----2----3----4----5 \tag{1}$

t = 0.5时刻，相遇：

$0----1--相遇--2----3----4----5 \tag{1}$

士兵1：

$-->0.5 \tag{2}$

士兵2：

$0.5<--\tag{3}$

此后，士兵1返回：

$1.5<--\tag{4}$

士兵2返回：

$-->3.5\tag{5}$

可以看到，士兵2不过是继续完成士兵1没有走完的路罢了，士兵1也在完成士兵2没走完的路，实际上问题可以简单等效为每个士兵选中一个方向，一直走到结束所花费的时间中，整体撤离的最短时间和整体撤离的最长时间。

士兵1实际时间：

士兵2实际时间：

士兵1本来时间：

士兵2本来时间：

由于士兵相遇前走过时间相同，相遇后相互成为对方，所以，士兵1和士兵2实际的时间刚好就是本来的时间互换。总之，相遇仅会改变士兵编号，对最终结果并无影响，所以这里我们可以直接遍历全部士兵求解时间。

2.编码求解

#include <stdio.h>

int math_min(int a,int b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

int math_max(int a,int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int main() {
    // 输入整数L,表示独木桥长度
    int L,N;
    int a[10000];
    // 输入整数，表示独木桥长度
    scanf("%d",&L);
    // 输入整数，表示人数
    scanf("%d",&N);
    for (int i = 0; i < N; i++) {
        scanf("%d",&a[i]);
    }
    // 输出最小时间和最大时间
    int min = 0;
    int max = 0;
    // min = 2;max=4;
    // 0---1---2---3---4---5
    // x---1---x---3---x---x
    // 最少时间是max(每个士兵的最少)
    // 最长时间是max(每个士兵的最长)
    // 遍历士兵，看看最短时间
    for (int i = 0; i < N; i++) {
        // 当前士兵选择不同方向的最少时间
        int c_min = a[i] < (L + 1 - a[i]) ? a[i]:(L + 1 - a[i]);
        // 当前士兵选择不同方向的最长时间
        int c_max = a[i] > (L + 1 - a[i]) ? a[i]:(L + 1 - a[i]);
        // 总体最短时间是每个人最短时间中最长的
        min = (min > c_min) ? min:c_min; 
        // 总体最长时间是每个人最长时间中最长的
        max = (max > c_max) ? max:c_max;
    }
    printf("%d %d\n",min,max);
}

DDqiuqiu

LG_P1007.独木桥

独木桥