Poj 3258 - River Hopscotch (跳房子 最大化最小值)

Poj 3258 - River Hopscotch

Description

Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance D_i from the start (0 < D_i < L).
To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.
Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).
FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

Input

Line 1: Three space-separated integers: L, N, and M
Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.

Output

Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks

Sample Input

25 5 2
2
14
11
21
17

Sample Output

4

奶牛跳房子：从N块石头中移除M块，使得间距最小值最大。
3.1不光是查找值！“二分搜索”
最大化最小值
https://entropy007.blogspot.com/2017/11/poj-3258-river-hopscotch.html

The "minimum is maximized" hints that this is a binary search problem. What are we searching for? The minimum distance possible between two consecutive dots after removing M elements. How are we going to find that? Test each minimum out. And how exactly do we do that? Well, we first sort out the array, accounting 0 and L, if we didn't do so. Then, we iterate through the array, counting the difference of any consecutive elements. If the difference is more than our guess, we increment a "rocks removed" counter by 1. Else, we update the "previous element" counter to this element. When done, if the rocks removed counter is more than M, this minimum is unfeasible, else, it is.

https://amoshyc.github.io/CPsolution/poj/p3258.html

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 的情況，我們可以預判掉這情形。

int L, N, M;
int rocks[MAX_N + 2];

bool C(int d) {
    int cnt = 0;
    int prev = 0; // 前一個石頭是誰，初使值為起點 rocks[0]
    for (int i = 1; i < N + 1; i++) {
        if (rocks[i] - rocks[prev] < d) // 若相鄰距離 < d，移除 rocks[i]。
            cnt++;
        else
            prev = i; // 維護前一個石頭
    }

    // 終點與其前一個的情況
    if (rocks[N + 1] - rocks[prev] < d) {
        cnt++;
        // prev = N + 1 // 後面沒石頭了，沒必要繼續維護
    }

    return cnt <= M;
}

int solve() {
    sort(rocks + 1, rocks + N + 1);

    if (C(L)) return L;

    // ... 1 1 1 1 0 0 0 ...
    int lb = 0, ub = L;
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) lb = mid;
        else ub = mid;
    }

    return lb;
}

int main() {
    scanf("%d %d %d", &L, &N, &M);
    for (int i = 1; i <= N; i++)
        scanf("%d", &rocks[i]);

    rocks[0] = 0;
    rocks[N+1] = L;

    printf("%d\n", solve());

    return 0;
}

http://www.cnblogs.com/kedebug/archive/2013/04/20/3032710.html

一条长为l（1~1,000,000,000）的河中，有n(1~50,000)块可垫脚的石头（不包括起始点和终点的），

给出它们与起始点的距离rock[i]，现在要你移除其中的m块，使得具有最小间距的相邻两块石头之间的距离最大。

思路：

1. 和 POJ 3273 一样的技巧，都是要 求“上（下）界的最小（大）值”问题，以后遇到类似的可以用二分的思路往上面靠;

2. 假设要输出的最终结果为 mid，则根据 mid 的值来确定最少需要去掉多少垫脚石。不断通过二分搜索来锁定最终的值;

3. 解题的时候要注意边界问题，相同符合条件的要尽量往最小（大）上面靠，就如同求：有序递增数组中 x 值的最小（大）下标一样;

http://blog.csdn.net/u014688145/article/details/73610408
属于二分，可以看作f(d)的一个函数，表示当前距离下，移除的石头，d越大，移除的石头也就越多。很明显是一种有序结构，所以直接在解空间中搜索满足条件的最小d即可
static int[] rocks; static int N; public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); int L = in.nextInt(); N = in.nextInt(); int M = in.nextInt(); rocks = new int[N + 2]; rocks[0] = 0; for (int i = 1; i <= N; ++i){ rocks[i] = in.nextInt(); } rocks[N+1] = L; Arrays.sort(rocks); lf = 0; rt = L; System.out.println(binarySearch(M)); } static int lf; static int rt; public static int binarySearch(int M){ while (lf < rt){ int mid = lf + (rt - lf + 1) / 2; if (remove(mid) > M) rt = mid - 1; else lf = mid; } if (remove(lf) <= M) return lf; return 0; } public static int remove(int d){ int cnt = 0; for (int i = 1, j = 0; i <= N + 1; ++i){ if (rocks[i] - rocks[j] < d){ cnt++; }else{ j = i; } } return cnt; }

http://blog.sina.com.cn/s/blog_6635898a0100kp1g.html

int main(){
    int l, n, m, i, rock[Max];
    scanf("%d%d%d", &l,&n,&m);
    for(i = 1; i <= n; i ++)
        scanf("%d", &rock[i]);
    rock[0] = 0;         //   将起始点的rock加入队列。
    rock[++n] = l;       //   将终点的rock加入队列。
    qsort(rock, 0, n);   //   对rock[]按从小到大快排。

    int mid, low = 0, high = l;
    while(high >= low){      //   二分， mid值为估计的最大距离值。
        mid = (high + low) / 2;
        int pre = 0, count = 0;    //   count为mid值所对应应该移开的rock数量。
        for(i = 1; i <= n; i ++){
            int dis = rock[i] - rock[pre];
            if(dis < mid) count ++;
            else pre = i;
        }
        if(count > m) high = mid - 1;
        else low = mid + 1;
    }
    printf("%d\n", high);
    return 0;
}