天天看點
傳回

二分答案引子概念練習

目錄

  • 引子
  • 概念
  • 練習
    • 練習一
      • 附加
    • 練習二
    • 練習三
    • 練習四
    • 練習五

引子

有這樣一個問題：題目連結

給出一個長度為N的正整數數組，不改變數組元素的順序，将這N個數分為K組。各組中元素的和分别為S1,S2…Sk。如何分組，使得S1至Sk中的最大值最小？

例如：1 2 3 4 5 6分為3組，{1 2 3} {4 5} {6}，元素和為6, 9, 6，最大值為9。也可以分為{1 2 3 4} {5} {6}。元素和為：10 5 6，最大值為10。是以第一種方案更優。并且第一種方案的最大值是所有方案中最小的。輸出這個最小的最大值。

  • 讀過問題發現這是一個最值問題，而且直接求解感覺無從下手，分組的方式多種多樣，周遊所有情況顯然是不合理的。
  • 要解決這個問題，可以利用一種正難則反的思想，直接求取困難，那麼能不能轉換成從後往前推呢？如果給我們一個答案，比如說我說最大值是10，那我這個是不是答案呢？事實上還可以找到最大值為9的情況，是以像這樣一點點的逼近正确答案就是二分答案的思想。

概念

  • 為什麼要叫二分答案？，因為就是求取答案，通過二分找答案，把合法的答案再二分尋找最優的合法。是以往往問題中會有類似最大的最小值或者最小的最大值之類的字眼，那麼這問題大機率就是二分答案了。
  • 二分答案大概的模闆如下： 
while(MIN<=MAX){
       int num = 0;
       int now = 0;
       mid = MIN + ((MAX - MIN) >> 1);//防溢出
       if(check(mid)){
           MAX = mid-1;
           ans = mid;//合法的解
       }else{
           MIN = mid+1;
       }
   }
  • 找到一個合法的解就把他記錄在ans中,在循環結束時ans即為最優解。
  • 二分答案思路看起來比較簡單，但是這其中的細節實難控制，比如為什麼while循環中是<=不是小于？有些網上代碼寫的是小于啊。為什麼MAX = mid - 1,MIN = mid + 1 而不是MAX = mid等等這類問題。對于上述相關問題，這裡不做細微讨論，這裡有一篇文章講的很詳細文章連結

練習

練習一

  • 上面的如果完全掌握了，那麼可以做相關的問題，回到最開始的問題
  • 題目中講不改變元素的順序，那麼我們就可以從頭開始一個一個計算，如果和超過mid，說明這個地方需要分，如果分組總數超過k說明不合法，否則合法。
  • 注意分組是從1開始分的。 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+100;
ll Data[MAXN];
ll low = 0,high = 5e14,mid;
ll ans;
int n,k;
bool check(ll m){
    ll sum = 0;
    int num = 1;
    for(int i=0;i<n;i++){
        if(sum + Data[i] > m){
            num++;
            sum = 0;
        }
        if(num > k) return false;
        sum += Data[i];
    }
    return true;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>Data[i];
    while(low<=high){
        mid = low + ((high - low) >> 1);
        if(check(mid)){//合法,是不是最小呢
            ans = mid;
            high = mid -1;
        }else low = mid + 1;
    }
    cout<<ans;
    return 0;
}

附加

題目連結

  • 突然發現這裡有一道一樣的問題，按照上面的程式交上去第四個點WA了，震驚！不得不說luogu上面題目資料還是很強的

    自造樣例：

    Input:

    2 2

    1 5

    Output:

    5

    實際輸出:1

  • 問題在于如果有個數特别大，甚至大于mid，就可能出問題，可以加個特判 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
int main(){
    int n, m;
    ll l, r, mid, ans; 
    l = 0;
    r = 1e13;       
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>Data[i];
    while(l <= r){
        mid = l + ((r - l) >> 1);
        ll sum = 0;
        int num = 1;
        for(int i=0;i<n;i++){
            if(Data[i] > mid){
                l = Data[i];
                goto here;
            }
            if(sum + Data[i] <= mid){
                sum += Data[i];
            }else{
                num++;
                sum = Data[i];
            }
        }if(num > m) l = mid + 1;
        else{
            ans = mid;
            r = mid - 1;
        }
        here:;
    }
    cout<<ans;
    return 0;
}
  • 但是最好的方法是直接讓l等于數組中最大的那一個，這樣肯定不會出現那樣的情況 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
bool check(int n, int m, ll mid){
    ll sum = 0;
    int num = 1;
    for(int i=0;i<n;i++){
        if(sum + Data[i] <= mid){
            sum += Data[i];
        }else{
            num++;
            sum = Data[i];    
            if(num > m) return false;
        }
    }
    return true;
}
int main(){
    int n, m;
    ll l, r, mid, ans; 
    l = 0;
    r = 1e13;       
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>Data[i];
        l = max(l, Data[i] * 1LL);
    }
    while(l <= r){
        mid = l + ((r - l) >> 1);
        if(check(n, m, mid)){
            ans = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    cout<<ans;
    return 0;
}

練習二

這道題是洛谷上的P2678題目連結：跳石頭

  • 這道題求得是最短跳躍距離的最大值，想到二分答案，需要注意的是我們需要從0跳到終點，是以數組元素應該是從0到終點之間所有石頭坐标再加上終點坐标，用一個now指針記錄目前的位置，如果發現跳的距離小于mid，說明石頭需要移動，貪心的思路，顯然我們需要移除右邊石頭，這樣一直移動下去最後和最大移動石頭數進行比較，如果大于，說明移動的多了，這說明mid取得太大，需要二分區間取左邊；如果小于等于，說明這是合法的解，那麼我們取右邊，看看有沒有更優解，因為問題求的是最短距離的最大值。 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int MAXN = 2e5+100;
int Data[MAXN];
int main(){
   int L,N,M;
   cin>>L>>N>>M;
   for(int i=1;i<=N;i++) cin>>Data[i];
   Data[0] = 0;
   Data[N+1] = L;
   int low,high;
   int ans;
   low = 0;
   high = L;
   while(low <= high){
       int mid = low + ((high - low) >> 1);
       int sum = 0;
       int now = 0;
       for(int i=1;i<=N+1;i++){
           if(Data[i] - Data[now] < mid){
               sum++;
           }else now = i;
           if(sum > M) break;
       }
       if(sum > M){
           high = mid - 1;
       }else{
           ans = mid;
           low = mid + 1;
       }
   }
   cout<<ans;
   return 0;
}

練習三

poj上的一道題1064

這題洛谷上也有一道切繩子

  • 這道題思路上和前面兩道題都是類似的，二分答案，不斷尋找合法的最優解，所不同的是這裡面涉及到了double類型的二分答案，這裡面就涉及到了精度的問題，如何去控制精度，精度太高可能會逾時，精度低可能會錯誤，這道題在洛谷上對精度沒有太高的要求，但是在poj上就不同了。
  • 下面是這道題的一般性寫法，需要注意的是最終輸出結果要求略去小數點兩位之後的數而不是四舍五入。 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int MAXN = 2e5+100;
double eps = 1e-8;
double Data[MAXN];
int main(){
    int n,k;
    cin>>n>>k;
    double MAX = 0;
    for(int i=0;i<n;i++){
        cin>>Data[i];
        MAX = max(MAX,Data[i]);
    }
    double low = 0;
    double high = 1e9;
    double ans;
    double mid;
    int T = 100;
    while(high - low >eps){
        int num = 0;
        mid = (low + high) / 2;
        for(int i=0;i<n;i++){
            num += (int) (Data[i] / mid);
        }
        if(num < k){
            high = mid;
        }else low = mid;
    }
    printf("%.2f",floor(mid*100)/100.0);
    return 0;
}

同樣的程式在POJ上卻不能通過，但是如果用一個for循環來代替while就可以消除high-low的精度問題。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
const int MAXN = 2e5+100;
double eps = 1e-8;
double Data[MAXN];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    double MAX = 0;
    for(int i=0;i<n;i++){
        scanf("%lf",&Data[i]);
        MAX = max(MAX,Data[i]);
    }
    double low = 0;
    double high = MAX;
    double ans;
    double mid;
    for(int j=0;j<100;j++){
        int num = 0;
        mid = (low + high) / 2;
        for(int i=0;i<n;i++){
            num += floor(Data[i] / mid);
        }
        if(num < k){
            high = mid;
        }else low = mid;
    }
    printf("%.2f",floor(mid*100)/100.0);
    return 0;
}

循環一百次，相當于2的100次方，大概是10的-30次方的精度，實測50次循環達到10的-15次方精度也無法通過這道題，更不要說設定的10的-8次方的精度了。

精度問題又是一個新的課題，對于一般的題目來說選取合适的精度就可以達到目的了。

練習四

洛谷P3853

這是一道比較正常的二分答案，練習此題目的在于熟悉自己的二分模闆

  1. 關于while帶不帶等号。由于區間是閉區間，是以帶等号
  2. 關于mid加減1的問題。閉區間，直接l=mid+1，r=mid-1防止循環出不來
  3. 需要注意一個地方，如果出現這種情況：開始路标坐标為0,100，空曠指數為50，那麼隻需要加一個路标就可以了，而不是（100-0）/50=2，是以坐标差整除空曠指數的時候num還要減一 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+100;
int Data[MAXN];
int main(){
    int L,N,K;
    cin>>L>>N>>K;
    for(int i=0;i<N;i++) {
        cin>>Data[i];
    }
    int l = 0;
    int r = L;
    int ans = 0;
    while(l <= r){
        int mid = l + ((r - l) >> 1);
        int num = 0;
        for(int i=1;i<N;i++){
            int tmp = Data[i] - Data[i-1];
            if(tmp > mid) {
                num += tmp / mid;
                if(tmp % mid == 0) num--;
            }
        }
        if(num <= K){
            ans = mid;
            r = mid - 1;
        }else l = mid + 1;
    }
    cout<<ans;
    return 0;
}

練習五

洛谷P3743

  • 這道題需要仔細了解題意，首先需要兩個數組a和b，a數組表示裝置每秒消耗多少能量，b數組表示裝置總共有多少能量，且能量勻速消耗，現在有一個充電器，它每秒鐘能充電p，也是勻速充電，将這些電器一起使用，問最多能使用多久才不會有電器電量減為0
  • 一個關鍵點是充電時間任意，這個條件使得問題大大簡化，那麼可以這樣考慮，如果電器能夠無限使用，那麼每秒鐘電器消耗的總電能應該要小于等于充電器每秒鐘能充電的電能，這是輸出-1的情況；如果不是無限使用，那麼需要二分答案，給我一個答案ans，我來判斷是否成立，這就需要周遊a數組，如果說在ans時間内，目前電器用電總量不到它開始時的總電量，那麼不需要處理，否則需要計算它需要充電的電量，把所有電器需要充電的電量累加起來，與充電器能充電的電量比較，如果大于說明使用時間長了，否則說明使用時間短了 
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5 + 100;
double eps = 1e-6;
double a[MAXN];
double b[MAXN];
bool check(double ans, int n, double p){
    double tot = 0;
    for(int i=0;i<n;i++){
        if(ans * a[i] <= b[i]) continue;
        tot += ans * a[i] - b[i];
    }
    if(tot < p * ans) return true;//ans合法,且可以繼續加大
    return false;
}
int main(){
    int n;
    double p;
    double tot = 0;
    scanf("%d%lf",&n,&p);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",a+i,b+i);
        tot += a[i];
    }
    if(tot <= p) printf("-1");
    else{
        double l = 0;
        double r = 1e10;
        double mid;
        while(r - l > eps){
            mid = (l + r) / 2;
            if(check(mid, n, p)){
                l = mid;
            }else r = mid;
        }
        printf("%.6f",mid);
    }
    return 0;
}
  • 精度控制一下，太小可能TLE
二分
上一篇: arch linux設定固定ip,Archlinux設定靜态固定IP
下一篇: codefroces767D 二分答案

繼續閱讀