Peking University Online Judge 3258 River Hopscotch
なぜか最近POJとの相性が良くなってきたので、ACコードを貼っていきます。
この問題は二分探索で通しました。
#include<iostream> #include<algorithm> using namespace std; static const int MAX_N = 100000; static const int MAX_D = 1000000000; int L, N, M; int D[MAX_N + 2]; int main(){ cin >> L >> N >> M; for(int i = 1; i < N + 1; i++) cin >> D[i]; D[0] = 0, D[N + 1] = L; sort(D, D + N + 2); int lb = 0, ub = MAX_D + 1; while(ub - lb > 1){ int mid = lb + (ub - lb) / 2; int cnt = 1; for(int i = 0; i < N + 2; i++){ int dist = mid; while(dist >= D[i + 1] - D[i] && i < N + 2){ dist -= D[i + 1] - D[i]; i++; } cnt++; } if(N + 2 - cnt >= M) ub = mid; else lb = mid; } cout << ub << endl; return 0; }