每年奶牛們都要舉辦各種特殊版本的跳房子比賽，包括在河里從一塊巖石跳到另一塊巖石。這項激動人心的活動在一條長長的筆直河道中進行，在起點和距離起點 L 遠的終點各有一塊巖石 (1 ≤ L ≤ 10^9)。在起點和終點之間，有 N 塊巖石 (0 ≤ N ≤ 50000)，每塊巖石與起點的距離分別為 Di (0 < Di < L)。

在比賽過程中，奶牛輪流從起點出發，嘗試到達終點，每一步只能從一塊巖石跳到另一塊巖石。當然，實力不濟的奶牛無法抵達終點，在河中間就退出比賽了。

農夫約翰為他的奶牛們感到自豪并且年年都觀看了這項比賽。但隨著時間的推移，看著其他農夫的膽小奶牛們在相距很近的巖石之間緩慢前行，他感到非常厭煩。他計劃移走一些巖石，使得從起點到終點的過程中，最短的跳躍距離最長。他可以移走除起點和終點外的至多 M 塊巖石 (0 ≤ M ≤ N)。

請幫助農夫約翰確定：移走這些巖石后，最短跳躍距離的最大值是多少？

輸入
第 1 行包含以單個空格分隔的三個整數 L, N, M。
第 2 到 N + 1 行，每行一個整數，表示每個巖石與起點的距離。不會有兩個巖石出現在同一個位置。
輸出
輸出一個整數，即最短跳躍距離的最大值。
示例輸入
25 5 2
2
14
11
21
17
示例輸出
4
提示
在移除位于 2 和 14 的兩塊巖石之后，最短跳躍距離達到了最大值 4 (從 17 到 21，或從 21 到 25)。

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int main() {int L,n,m;while(cin>>L>>n>>m){int a[50005];a[0]=0;for(int i=1;i<=n;++i)scanf("%d",&a[i]);a[n+1]=L;sort(a,a+n+2);int low=0,high=L,mid;while(low<=high){mid=low+(high-low)/2;/* int ans=0,tag=a[0];int sum=0;for(int i=1;i<=n+1;){if(mid>=(sum+=a[i]-a[i-1]))//在網上看的這個思想也挺好{i++;ans++;}else{i++;sum=0;} //tag=a[i];}*/int ans=0,tag=a[0];for(int i=1;i<=n+1;++i){if(mid>=a[i]-tag){//tag=a[i-1];自己寫的這個思想，開始是個bug,原因是這行代碼不應該加ans++;}elsetag=a[i];}//cout<<mid<<endl;if(ans<=m){//cout<<mid<<endl;low=mid+1;}elsehigh=mid-1;}cout<<low<<endl;}return 0; }

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的poj3258 River Hopscotch (二分搜索，考虑最大值最小问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。