一個(gè)不錯(cuò)的二分,注釋在代碼里

#include <stdio.h> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> using namespace std; ///二分搜索答案，最大化最小值 int main() {int L,n,m;int a[50010];while(~scanf("%d %d %d",&L,&n,&m)){for(int i = 1; i <= n; i++)scanf("%d",&a[i]);a[0] = 0;a[n+1] = L;sort(a,a+n+2);/*for(int i = 0;i <= n+1;i++)cout<<a[i]<<" ";cout<<endl;*/int l = 0,r = L,mid;///先模擬一個(gè)最小值mid，假設(shè)它就是正確答案int num;while(l <= r){int last = 0;int sum = 0;mid = (l + r) / 2;for(int i = 1; i <= n+1; i++){if(a[i] - a[last] < mid)///如果比mid小，就將該節(jié)點(diǎn)強(qiáng)制刪除，并計(jì)數(shù)sum++;else last = i;///如果不是就更新，為啥要更新，如果不更新，那我們計(jì)算的///就不是兩點(diǎn)之間的距離了啊 }if(sum > m)///刪多了，說明mid值偏大r = mid - 1;else{l = mid + 1;num = mid;}}///最后經(jīng)過二分循環(huán)，得到最大的mid；printf("%d\n",num);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/jifahu/p/5449049.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3258 River Hopscotch（二分查找答案）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。