POJ 3258 - River Hopscotch

http://poj.org/problem?id=3258

概要

幅 \(L\) の川に \(N\) 個の石がそれぞれ位置 \(D_i\) に置かれている。 片方の岸から石の上を飛び移りながらもう片方の岸へ行きたい。 ここから \(M\) 個の石を取り除いたときの、ジャンプする必要のある最小の距離の最大値を答える。

制約

• \(1 \le L \le 10 ^ 9\)
• \(0 \le N \le 5 \cdot 10 ^ 4\)
• \(0 \le D_i < L\)

解法

最小値の最大化なので二分探索。 ジャンプする必要のある最小の距離 \(l\) が達成できるかどうかは、 隣り合う石の距離が \(l\) 未満になるような石を貪欲に取り除いていき、 取り除いた数が \(M\) 以下かどうかを調べればいい。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 bool ok(const vector<int>& v, int M, int l)
 7 {
 8   int prev = 0;
 9   int c = 0;
10   for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
11     const int d = *it - prev;
12     if (d < l) {
13       // remove
14       ++c;
15     } else {
16       prev = *it;
17     }
18   }
19   return c <= M;
20 }
21 
22 int main()
23 {
24   int L, N, M;
25   cin >> L >> N >> M;
26   vector<int> v(N);
27   for (int i = 0; i < N; i++) {
28     cin >> v[i];
29   }
30 
31   sort(v.begin(), v.end());
32   int lo = 0, hi = L;
33   while (lo < hi) {
34     const int mid = (lo + hi + 1)/2;
35     if (ok(v, M, mid)) {
36       lo = mid;
37     } else {
38       hi = mid-1;
39     }
40   }
41   cout << lo << endl;
42   return 0;
43 }