P1007 獨木橋 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

題目背景

戰爭已經進入到緊要時間。你是運輸小隊長，正在率領運輸部隊向前線運送物資。運輸任務像做題一樣的無聊。你希望找些刺激，于是命令你的士兵們到前方的一座獨木橋上欣賞風景，而你留在橋下欣賞士兵們。士兵們十分憤怒，因為這座獨木橋十分狹窄，只能容納?11?個人通過。假如有?22?個人相向而行在橋上相遇，那么他們?22?個人將無法繞過對方，只能有?11?個人回頭下橋，讓另一個人先通過。但是，可以有多個人同時呆在同一個位置。

題目描述

突然，你收到從指揮部發來的信息，敵軍的轟炸機正朝著你所在的獨木橋飛來！為了安全，你的部隊必須撤下獨木橋。獨木橋的長度為?L，士兵們只能呆在坐標為整數的地方。所有士兵的速度都為?11，但一個士兵某一時刻來到了坐標為?0?或?L+1?的位置，他就離開了獨木橋。

每個士兵都有一個初始面對的方向，他們會以勻速朝著這個方向行走，中途不會自己改變方向。但是，如果兩個士兵面對面相遇，他們無法彼此通過對方，于是就分別轉身，繼續行走。轉身不需要任何的時間。

由于先前的憤怒，你已不能控制你的士兵。甚至，你連每個士兵初始面對的方向都不知道。因此，你想要知道你的部隊最少需要多少時間就可能全部撤離獨木橋。另外，總部也在安排阻攔敵人的進攻，因此你還需要知道你的部隊最多需要多少時間才能全部撤離獨木橋。

算法思路

首先，我們要明白一件事情：

某一次行走的時間，一定是其中所用時間最長的人花費的時間

那么，時間最小就代表每個人朝離ta最近的出口走，這個時候不管L有多長，也不會出現相遇，為什么呢？假設有一個人往L+1方向走，那么ta右邊的所有人都是往L+1方向走的，速度又相同，不會撞在一起。

ans=max(min(l+1-a,a),ans);

時間最長呢？這個時候絕對會相遇，怎么辦呢？我們想想，a與b相遇，a和b分別向各自相反方向行駛，則a的反方向就是b的原方向。a和b撞在一起后，我們把a看成b，b看成a，這樣就相當于相遇后不回頭，繼續走了。

ans=max(max(l+1-a,a),ans);

代碼就成這樣了，

#include<bits/stdc++.h>
using namespace std;
int n,l,ans1=0,ans2=0;
int main()
{cin>>l>>n;for(int i=1;i<=n;i++){int a;cin>>a;ans1=max(min(l+1-a,a),ans1);ans2=max(max(l+1-a,a),ans2);}cout<<ans1<<' '<<ans2;
}

希望這些對大家有用，三連必回