蓝桥杯-导弹拦截-贪心

本文主要是介绍蓝桥杯-导弹拦截-贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥杯-导弹拦截-贪心-dp-java

算法训练拦截导弹

时间限制：1.0s 内存限制：256.0MB

问题描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

　　输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，为导弹依次飞来的高度

输出格式

两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

解题思路：这题的本质就是最长下降子序列

下降上升都一样这个不是重点

求解此类问题有两种方式

1.dp n*n 时间复杂度

1–n 第i个位置的最长子序列 = max（1— i-1）+1

2.二分查找 n*logn时间复杂度

建立一个空数组每次放在数组的数都和最后一个数进行比较符合要求就放入数组的末尾

不符合要求就进入此时的数组进行二分查找那么找啥呢？看要求比如本题求的是最长下降子序列那么就找

比他大的第一个数的位置+1 的位置然后将此位置的值换成他就可以了如果不明白可以自己找点数模拟一遍就很好懂

注意：我写此题的时候用的是第二种但这是不对的这种方法只能求序列第一遍的最大子序列的长度注意是长度

所以这个不能这么用

下面是ac代码有一部分注释

import java.util.ArrayList;
import java.util.Scanner;

public class Main{

   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner scanner = new Scanner(System.in);
       while (scanner.hasNext()) {
           String [] str = scanner.nextLine().split(” “);
           int [] arr = new int [str.length];
           for (int i = 0; i < arr.length; i++) {
               arr[i] = Integer.parseInt(str[i]);
           }
           boolean [] flag = new boolean [arr.length];//记录已经被拦截的导弹
           int max = 0;//最大下降子序列的长度
           int num = 0;//需要几套导弹系统
           int sum = 0;//记录导弹拦截总数用于跳出while循环
           while (sum != arr.length) { //当所有导弹被拦截就结束循环
               ArrayList [] lists = new ArrayList [arr.length];
               for (int i = 0; i < lists.length; i++) {
                   lists[i] = new ArrayList<Integer>();
               }//记录每个子序列
               int index = 0; //最大子序列的下标
               int childMax = 0; //最大子序列的长度
               int k = 0;
               for (int i = 0; i < arr.length; i++) {
                   if (flag[i]) {
                       continue;
                   }
                   if (k == 0) {
                       k ++;
                       lists[i].add(i);
                       childMax = 1;
                       index = i;
                   }else {
                       int maxLength = -1;
                       int maxIndex = -1;
                       for (int j = i-1; j >= 0; j–) {
                           if (flag[j]) {
                               continue;
                           }
                           if (arr[i] < arr[j]) {
                               maxLength = maxLength > lists[j].size() ? maxLength : lists[j].size();
                               maxIndex = maxLength > lists[j].size() ? maxIndex : j;
                           }
                       }
                       if (maxIndex == -1) {
                           lists[i].add(i);
                       }else {
                           for (int j = 0; j < lists[maxIndex].size(); j++) {
                               lists[i].add(lists[maxIndex].get(j));
                           }
                           lists[i].add(i);
                       }
                       childMax = childMax > lists[i].size() ? childMax : lists[i].size();
                       index = childMax > lists[i].size() ? index : i;
                   }
               }
               for (int i = 0; i < lists[index].size(); i++) {
                   flag[(int) lists[index].get(i)] = true;
               }
               max = max > childMax ? max : childMax;
               num ++;
               sum += childMax;
           }
           System.out.println(max + “\n” + num);
       }
   }

}