通过数:1

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

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

1049: B13-二分-跳石头游戏(二分答案)

题目描述

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


样例输入

25 5 2
2
14
11
21
17

样例输出

4

提示

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

参考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

07-19 11:09