P1007 独木桥

Koei · 2025-10-05 19:52:42 · 算法·理论

题意：

有n名士兵在线段上，士兵i可以往左边或右边任意一边移动，当两名士兵相遇时他们会分别转身

问：最少要多少时间，最久要多少时间

思路：

首先发现当两名士兵相遇时,因为两人都要转向，而两名士兵的速度、特征都相等，所以我们可以当这两名士兵是直接穿过对方继续前进

既然士兵可以直接穿过其他士兵，这就说明每个士兵都是独立的个体，所以士兵i到桥两边的时间就是他直接走到桥两边的时间

所以最少的时间就是每名士兵离开桥的小值的最大值，即：

minn=max(minn,min(a[i],l-a[i]+1));

最大的时间就是每名士兵离开桥的大值的最大值，即：

maxx=max(maxx,max(a[i],l-a[i]+1));

程序：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int l,n,minn(0),maxx(0);
int a[maxn];
int main(){
    cin>>l>>n;
    for(int i(1);i<=n;i++){
        cin>>a[i];
        // cout<<l-a[i]+1<<'\n';
        minn=max(minn,min(a[i],l-a[i]+1));
        maxx=max(maxx,max(a[i],l-a[i]+1));
    }
    cout<<minn<<' '<<maxx<<'\n';
    return 0;
}