River Hopscotch POJ3258
投稿日： 更新日:
問題：http://poj.org/problem?id=3258
解法
最小の距離を以上にできるかを二分探索します。
隣あう石の距離が未満の時に石を貪欲に取り除きます。そして、取り除いた石の個数が以下か判定します。
実装
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int l, n, m;
cin >> l >> n >> m;
vector<int> d(n);
for(int i = 0;i < n; ++i){
cin >> d[i];
}
sort(d.begin(), d.end());
int ok = 0, ng = 1e9 + 10;
while(ng - ok > 1){
int mid = (ok + ng)/2;
int old = 0;
int count = 0;
for(int i = 0;i < n; ++i){
if(d[i] - old < mid){
count++;
}else{
old = d[i];
}
}
if(l - old < mid)count++;
if(count <= m){
ok = mid;
}else{
ng = mid;
}
}
cout << ok << endl;
return 0;
}