[Java] 蓝桥杯ALGO-13 算法训练拦截导弹

问题描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，为导弹依次飞来的高度
输出格式
两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2

package algo13;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] missile = reader.readLine().split(" ");
        reader.close();
        int[] high = new int[missile.length];
        for (int i = 0; i < high.length; i++) {
            high[i] = Integer.parseInt(missile[i]);
        }
        System.out.println(getMaxIntercept(high));
        System.out.println(getNumberOfIntercepter(high));
    }
    
    private static int getMaxIntercept(int[] high) {
        int[] dp = new int[high.length];
        int max = 0;
        for (int i = 0; i < high.length; i++) {
            for (int j = i + 1; j < high.length; j++) {
                if (high[j] <= high[i]) {
                    dp[j] = Integer.max(dp[j], dp[i] + 1);
                    max = Integer.max(max, dp[j]);
                }
            }
        }
        return max + 1;
    }
    
    private static int getNumberOfIntercepter(int[] high) {
        int numberOfIntercepter = 0;
        boolean[] isIntercept = new boolean[high.length];
        for (int i = 0; i < high.length; i++) {
            int midHighDifference = getMinHighDifference(high, i, isIntercept);
            if (midHighDifference == -1) {
                numberOfIntercepter++;
            } else {
                isIntercept[midHighDifference] = true;
            }
        }
        return numberOfIntercepter;
    }
    
    private static int getMinHighDifference(int[] high, int pos, boolean[] isIntercept) {
        int minHighDifferenceIndex = -1;
        for (int i = 0; i < pos; i++) { if (isIntercept[i] == false && high[i] >= high[pos]) {
                if (minHighDifferenceIndex == -1 || high[i] < high[minHighDifferenceIndex]) {
                    minHighDifferenceIndex = i;
                }
            }
        }
        return minHighDifferenceIndex;
    }
}

package algo13;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String[] missile = reader.readLine().split(" ");

reader.close();

int[] high = new int[missile.length];

for (int i = 0; i < high.length; i++) {

high[i] = Integer.parseInt(missile[i]);

}

System.out.println(getMaxIntercept(high));

System.out.println(getNumberOfIntercepter(high));

}

private static int getMaxIntercept(int[] high) {

int[] dp = new int[high.length];

int max = 0;

for (int i = 0; i < high.length; i++) {

for (int j = i + 1; j < high.length; j++) {

if (high[j] <= high[i]) {

dp[j] = Integer.max(dp[j], dp[i] + 1);

max = Integer.max(max, dp[j]);

}

return max + 1;

}

private static int getNumberOfIntercepter(int[] high) {

int numberOfIntercepter = 0;

boolean[] isIntercept = new boolean[high.length];

for (int i = 0; i < high.length; i++) {

int midHighDifference = getMinHighDifference(high, i, isIntercept);

if (midHighDifference == -1) {

numberOfIntercepter++;

} else {

isIntercept[midHighDifference] = true;

}

return numberOfIntercepter;

}

private static int getMinHighDifference(int[] high, int pos, boolean[] isIntercept) {

int minHighDifferenceIndex = -1;

for (int i = 0; i < pos; i++) { if (isIntercept[i] == false && high[i] >= high[pos]) {

if (minHighDifferenceIndex == -1 || high[i] < high[minHighDifferenceIndex]) {

minHighDifferenceIndex = i;

}

return minHighDifferenceIndex;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版