【NOIP2015】【Luogu2678】跳石头

problem

solution

codes

//二分答案
//QAQ注意：起点和终点也是有石头的w
#include<iostream>
#include<algorithm>
#define maxn 100010
using namespace std;
int ll, n, m;
int a[maxn];
bool check(int x){
    int t=0, co=0; //起点的石头不能搬走哦
    for(int i = 1; i <= n+1; i++){
        if(a[i]-a[t]<x)co++;//如果距离小于我二分的答案x，那么这块石头需要搬走
        else t = i;//不然我就跳过来
    }
    if(co > m)return false;//如果要搬走的石头多于m块，那么这个解太大了
    return true;
}
int main(){
    cin>>ll>>n>>m;
    for(int i = 1; i <= n; i++)cin>>a[i];
    a[n+1] = ll;
    sort(a,a+n+1);  //排个序防炸输入数据
    int l = 1, r = ll;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid))l = mid+1;
        else r = mid-1;
    }
    cout<<r<<"\n";
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80404449