7月18日刷题记录 二分答案跳石头游戏Getting

通过数：1

明天就要暑假编程集训啦~莫名开心

今天做出了一道 二分答案题（好艰辛鸭）

1049: B13-二分-跳石头游戏（二分答案）

题目描述

样例输入

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