题目描述

算法代码

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
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
//题目要求什么 就对什么进行二分
//分析题目意义 意思为找出又一个最短距离ans 使得每个石头的两两相应距离x 都比这个ans大  并且这个最短距要最大   求区间最大值 此时区间的单调性都为单调递增 因此得出结论可以使用二分算法
const int N=50010;
int   shitou[N];
int  l,n,m;
bool check(int mid)
{    int use=0;
     int first=0;  //从起点开始遍历
    for(int i=1;i<=n;i++)
        {   if(shitou[i]-first<mid) { use++; }//如果有一对石头的相邻距离比这个二分的距离小 那么不符合要求
            else first=shitou[i];


        }

    return use<=m;


}


int main()
{  cin>>l>>n>>m ;
   for(int i=1;i<=n;i++)
      {  
            cin>>shitou[i];  
      }
      shitou[++n]=l;  //最后一个终点的坐标
     int l=0;int r=1e9+10;
     while(l<r) 
     {  int mid=l+r+1>>1;
        if(check(mid)) l=mid;
         else  r=mid-1;

     }

   cout<<r;

}

图解