7月18日刷題記錄 二分答案跳石頭遊戲Getting

通過數：1

明天就要暑假程式設計集訓啦~莫名開心

今天做出了一道 二分答案題（好艱辛鴨）

1049: B13-二分-跳石頭遊戲（二分答案）

時間限制: 5 Sec  記憶體限制: 256 MB

送出: 30  解決: 12

[送出] [狀态] [讨論版] [命題人:外部導入]

題目描述

樣例輸入

25 5 2
2
14
11
21
17      

樣例輸出

4      

提示

參考check函數：

    bool check(int x)

{ 

    int tot=0;

    if(tot>m)return 0;

    int last=0;

    for(int i=1;i<=n;i++)

        if(a[i]-a[last]<x)

        {

            tot++;

            if(tot>m)return false;

        }

        else last=i;

    return true;

}

/*
1049: B13-二分-跳石頭遊戲（二分答案）
時間限制: 5 Sec  記憶體限制: 256 MB
送出: 26  解決: 11
[送出] [狀态] [讨論版] [命題人:外部導入]
題目描述



樣例輸入

25 5 2
2
14
11
21
17


樣例輸出

4


提示

參考check函數：

bool check(int x)
{ 
    int tot=0;
    if(tot>m)return 0;
    int last=0;
    for(int i=1;i<=n;i++)
        if(a[i]-a[last]<x)
        {
            tot++;
            if(tot>m)return false;
        }
        else last=i;
    return true;
}

來源/分類
B13-二分 

[送出] [狀态]
*/ 
#include<bits/stdc++.h>
using namespace std;
int L,n,m,a[50005];
bool check(int x)
{ 
    int tot=0;
    int last=0;
    for(int i=1;i<=n;i++)
        if(a[i]-a[last]<x)
            tot++;
        else last=i;
    if(tot>m)return false;
    return true;
}
int main(){
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    a[n+1]=L;
    int l=0,r=L+1,ans;//那個+1 資料有些坑。。。
    while(l<r){
        
        int mid=(l+r)>>1;
    //    cout<<l<<" "<<r<<" "<<mid<<" "<<check(mid)<<endl;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else
            r=mid;
        
    }
    cout<<ans;
    return 0;
}      

啟示：①要仔細讀題和樣例解釋

②在調試代碼的過程中如果一眼找不出錯誤來，當然也不知道程式運作過程中變量數值的變化情況 ，就可以在程式運作時列印變量值←好方法！

還是繼續加油吧886         23:45 Program