跳房子游戏

x33g5p2x  于2022-08-17 转载在 其他  
字(1.4k)|赞(0)|评价(0)|浏览(359)

一 问题描述

二 算法设计

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;
    }
}

四 测试

相关文章

微信公众号

最新文章

更多