noip题库 —— 1.11河中跳房子
1、题目大意:就是给你一条线段,上面有一堆点,然后要删一些点,使得最长的相邻两点距离最短,最多删m个点
2、分析:这道题怎么做呢,其实很简单,就是一个二分答案,然后判断一下,怎么判呢,就是如果这个点和前面那个没被删的点
之间如果小于我们二分的值,就删了这个点。。
就是这样
3、代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100000];
int l, n, m;
bool hehe(int st){
int del = 0;
int front = 0;
for(int i = 2; i < n; i ++){
if(a[i] - front >= st) front = a[i];
else del ++;
}
if(a[n] - front < st) del ++;
if(del <= m) return true;
return false;
}
int main(){
scanf("%d%d%d", &l, &n, &m);
a[1] = 0;
for(int i = 2; i <= n + 1; i ++){
scanf("%d", &a[i]);
}
a[n + 2] = l;
n += 2;
int L = 1, R = l;
while(L < R){
int mid = (L + R) / 2;
if(mid == L) mid ++;
if(hehe(mid)) L = mid;
else R = mid - 1;
}
printf("%d\n", L);
return 0;
}