poj3258 River Hopscotch(二分最小值,好题)

时间:2022-11-23 22:17:26

https://vjudge.net/problem/POJ-3258

二分最小值,判断需要删去的点的个数,如果大于给定,则直接return 0,则说明该数需要再小。

最后注意,起点是0终点是l,起点可以不加进数组,终点必须加进去!!

 #include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int l, n, m;
int a[];
int C(int x)
{
int pre=, ans=;
for(int i = ; i <= n; i++){//真正的末尾是l!!!
if(a[i]-pre<x){//距离<x,应该消去
ans++;
}
else{
pre = a[i];
}
if(ans > m){
return ;
}
}
return ;
}
int main()
{
cin >> l >> n >> m;
for(int i = ; i < n; i++){
cin >> a[i];
}
a[n] = l;
sort(a, a+n+);
int lb = , ub = INF;
while(ub-lb>){
int mid = (lb+ub)>>;
if(C(mid)){
lb = mid;
}
else{
ub = mid;//如果不满足就说明该数还要再小
}
}
cout << lb << endl;
return ;
}