P2678 [NOIP2015 提高组] 跳石头 二分答案

题目：


思路：
依旧是对答案可能的范围进行二分，然后代入并求取需要搬掉多少石头。
AC代码：

#include<cstdio>
#include <iostream>
#include<cstring>
#include<algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=111111;
int d,n,m,a[maxn],dis[maxn];
int maxx=-0x3f3f3f3f;
bool check(long long x)
{
    int cnt=0;for(int i=1;i<=n;i++) dis[i]=a[i]-a[i-1];dis[n+1]=d-a[n];//for(int i=1;i<=n+1;i++) cout<<"i="<<i<<" "<<dis[i]<<endl;for(int i=1;i<=n+1;i++){
    if(dis[i]<=x){
    //cout<<"i="<<i<<" "<<"dis[i]"<<dis[i]<<endl;cnt++;dis[i+1]+=dis[i];} }//cout<<"cnt="<<cnt<<endl;if(cnt<=m) return 1;return 0;
}
int main()
{
    cin>>d>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int l=0,r=d;while (l<r){
    long long mid=l+((r-l)>>1);//cout<<"mid="<<mid<<" "<<"check(mid)="<<check(mid)<<endl;if(!check(mid)) r=mid;else l=mid+1;//cout<<"l="<<l<<" "<<"r="<<r<<endl;}if(l==r) cout<<l<<endl;return 0;
}