Algoogle

Algorithm for Programming Contest

PKU 3258 River Hopscotch

Category: PKU Tag: binary-search

River Hopscotch

問題概要


解法


距離の最小を二分探索する.
その値より小さい区間を消していって, 最終的に取り除いた石の数がMより大きいかどうか判定する.

####


(3258.cpp) download
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
#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i,a) for(int i = 0;i < (a); i++)
#define all(u) (u).begin(),(u).end()
#define pb push_back
using namespace std;
typedef vector<int> vi;

int L, N, M;
vi dist;

bool can(int len){
    int prev = 0;
    int cnt = 0;
    rep(i,N){
        if(dist[i] - prev < len) cnt++;
        else prev = dist[i];
    }
    return cnt <= M;
}

int main(){
    cin >> L >> N >> M;
    rep(i,N){
        int t; cin >> t;
        dist.pb(t);
    }
    sort(all(dist));
    int lb = 0, ub = L;
    while(lb < ub){
        int mid = (lb + ub + 1) / 2;
        if(can(mid)) lb = mid;
        else ub = mid - 1;
    }
    cout << lb << endl;
    return 0;
}

Comments