跳房子游戏_跳房子js

一 问题描述

二 算法设计

1 如果移除石头数等于总石头数（M=N），则直接输入L。

2 增加开始（0）和结束（N+1）两块石头，到开始节点的距离分别为 0 和 L。

3 对所有的石头都按照从开始节点的距离从小到大排序。

4 让 left = 0，right=L，如果 right-left>1，则 mid=（right+left）/2,判断是否满足移除 M 块石头之后，任意间距都小于 mid。如果满足，则说明距离还可以更大，让 left = mid；否则让 right = mid，继续进行二分搜索。

5 搜索结束后， left 就是母牛必须跳跃的最短距离的最大值。

三 代码

package com.platform.modules.alg.alglib.poj3258;
 
import java.util.Arrays;
 
public class Poj3258 {
    public String output = "";
    private final int maxn = 50050;
    private Integer L;
    private Integer n;
    private Integer m;
    private Integer dis[] = new Integer[maxn];
 
    public Poj3258() {
        for (int i = 0; i < dis.length; i++) {
            dis[i] = 0xFFFFFFF;
        }
    }
 
    public String cal(String input) {
        String[] line = input.split("\n");
        String[] line1 = line[0].split(" ");
        L = Integer.parseInt(line1[0]);
        n = Integer.parseInt(line1[1]);
        m = Integer.parseInt(line1[2]);
 
        if (n == m) {
            return L.toString();
        }
        for (int i = 1; i <= n; i++) {
            dis[i] = Integer.parseInt(line[i]);
        }
        dis[0] = 0; // 增加开始点
        dis[n + 1] = L; // 增加结束点
        Arrays.sort(dis, 0, n + 1);
        //sort(dis, dis + n + 2);
        Integer left = 0;
        Integer right = L;
        while (right - left > 1) {
            int mid = (right + left) / 2;
            if (judge(mid))
                left = mid;//如果放得开，说明x还可以更大
            else
                right = mid;
        }
        return left.toString();
    }
 
    boolean judge(int x) { //移除m个石头之后，任意间距不小于x
        int num = n - m; //减掉m个石头，放置num个石头，循环num次
        int last = 0; //记录前一个已放置石头下标
        for (int i = 0; i < num; i++) { //对于这些石头，要使任意间距不小于x
            int cur = last + 1;
            while (cur <= n && dis[cur] - dis[last] < x) //放在第1个与last距离>=x的位置
                cur++; //由cur累计位置
            if (cur > n)
                return false; //如果在这个过程中大于n了，说明放不开
            last = cur; //更新last位置
        }
        return true;
    }
}

四 测试