蓝桥杯——又是二分
题目
答案
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int L,n,M;
int a[N];
bool check(int x)
{
int i = 0,now = 0;
int cnt = 0;//搬走石头的数目
while(i<n+1)
{
i++;
if(a[i]-a[now]>=x) now=i;
else {
cnt++;
}
}
if(cnt <= M) return true;
else return false;
}
int main() {
cin >> L >> n >> M;//N总长度N石头数量M主办方要搬的数量
for(int i = 1;i <= n; i++)
{
cin >> a[i];
}
a[0]=0;
a[n+1] = L;
int l = 0,r=L+1;
while(l+1<r)
{
int mid = (l+r)/2;
if(check(mid)) l = mid;
else r = mid;
}
if(check(r)) cout << r;
else cout << l;
return 0;
}判断界限
