[POJ] 3258. River Hopscotch — amoshyc's CPsolution 1.0 documentation

[POJ] 3258. River Hopscotch — amoshyc's CPsolution 1.0 documentation

最小值最大化，標準的二分搜。 二分搜教學請參 這

判斷函式為:

bool C(int d) = 移除 M 個石頭後，可否能使相鄰石頭間的最短距離 >= d。 

該函式明顯有單調性，相鄰石頭間的最短距離 d 越小越容易達成。

這個函式可以用 Greedy 實作:

從左至右迭代「起點終點外」的每個石頭 rocks[i]， 若該石頭與前一個石頭的距離 < d，我們必需移除該石頭，才能使相鄰石頭的距離 >= d。 我們計算總共有多少個石頭要移除，該個數必需 <= M。 

實作時，有兩點要注意:

1. 若 rocks[i - 1], rocks[i], rocks[i + 1] 中，rocks[i] 被移除了，    那 rocks[i + 1] 的前一顆石頭是 rocks[i - 1]，而不是 rocks[i]。  2. 上述演算法沒考慮到終點與其前一個石頭。    設中間那 N 個石頭中，最後面的那個石頭為 rocks[-2]，若與終點那石頭的距離 < d，    則要移除的是 rocks[-2]，而不是終點的石頭，因為終點那個石頭是不能移除的。 

---

解的空間 [0, L]。 下界即為在還沒移除任何石頭前，相鄰石頭間最短距離，但要計算出此值還得多打一些程式碼， 而我們知道此值必大於 0，反正 C(0) = 1，所以可以直接將下界設為 0。 上界發生在 M = N 時，相鄰石頭間最短距離即為 L。

C(d) 在解的空間 [0, L] 上的分佈為:

... 1 1 1 0 0 0 0 ... 

我們的目標是求左邊數來的最後一個 1 在哪？

另外，存在全部都為 1 的情況，我們可以預判掉這情形。

Read full article from [POJ] 3258. River Hopscotch — amoshyc's CPsolution 1.0 documentation