[Luogu-P1007]题解(C++)

静谧幽蓝 / 2023-05-06 / 原文

Part I Preface

原题目(Luogu)

Part II Sketch

给定一个正整数 \(L\)，表示独木桥长度。
给定一个正整数 \(N\)，表示桥上士兵的数量。
给定 \(N\) 个整数，分别表示每个士兵的坐标。
规定走到 \(0\) 坐标或 \(L+1\) 的位置为下桥，两个士兵相遇时不能走过去，他们会各自回头走。求出所有士兵撤离独木桥的最短时间，和最大时间（行走一个单位花费 \(1\) 个时间单位）。

Part III Analysis

嗯，看到这道题我不禁对这道题的普及-难度非常怀疑。啥？大模拟？
自己观察，不难发现两个人相遇的时候，左面的人相当于继承右面的人继续走，右面的人也一样，所以其实这个转向和最终的结果没有任何关系。我们只要求出一个人到底是向左走还是向右走下桥那个更快哪个更慢，记录下来即可。
向左下桥，要走 \(pos\) 单位，向右走下桥要走 \(L - pos + 1\) 单位。
设最小值为 \(min\_\)，最大值为 \(max\_\)。那么每次更新时依据 \(max\_ = max(max\_, max(L - pos + 1, pos)), min\_ = max(min\_, min(L - pos + 1, pos))\)
很巧妙的一题，建议大家去补。

Part IV Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int L, N, pos;
int max_ = 0, min_ = 0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> L >> N;
    for(int i = 1; i <= N; i++){
        cin >> pos;
        max_ = max(max_, max(L - pos + 1, pos));
        min_ = max(min_, min(L - pos + 1, pos));
    }
    cout << min_ << ' ' << max_;
    return 0;
}