蓝桥杯算法训练拦截导弹

客官°小女子只卖身不卖艺 2022-06-01 09:10 255阅读 0赞

转载自：[http://www.stdal.com/archives/118][http_www.stdal.com_archives_118]

![这里写图片描述][SouthEast]

算法演示

上面样例数据，算法处理过程如下

1、读入数据65

resv数据为空，直接将65装入

![这里写图片描述][1516944748690565.png]

2、读入数据158  
该项大于所有解的最大值，在resv\[0\]的基础上追加新的解

![这里写图片描述][1516945168850410.png]

3、读入数据170  
该项大于所有解的最大值，在resv\[1\]的基础上追加新的解

![这里写图片描述][1516945430308910.png]

4、读入数据299  
该项大于所有解的最大值，在resv\[2\]的基础上追加新的解

![这里写图片描述][1516945657855049.png]

5、读入数据300  
该项大于所有解的最大值，在resv\[3\]的基础上追加新的解

![这里写图片描述][1516945679899534.png]

6、读入数据155  
该项在i = 1时，大于前一项的最大值（65），并且小于当前项的最大值（158），说明该项解更优。则修改i = 1的解，将在前一项（0）解的基础上追加155，并覆盖掉当前1的解，即在65后面添加155，并替换掉解1的当前项65 158，变成了65 155

![这里写图片描述][1516945862220403.png]

7、读入数据207  
该项在i = 3时，大于前一项的最大值（170），并且小于当前项的最大值（299），说明该项解更优。则修改i = 3的解，将在前一项（2）解的基础上追加207，并覆盖掉当前3的解，即在65 158 170后面添加207，并替换掉解3的当前项65 158 170 299，变成了65 158 170 207

![这里写图片描述][1516945969569348.png]

8、读入数据389  
该项大于所有解的最大值，在resv\[4\]的基础上追加新的解

![这里写图片描述][1516946088860765.png]

这样就得到了最优解389 300 299 170 158 65，长度为6

之后对于原数据删除389 300 299 170 158 65，对于剩余数据207 155再执行上面的操作，直到没有剩余数据位置，此时执行算法的次数就是需要的台数

可见，对于以上数据，需要执行两次该算法才能使剩余数为空，所以需要的台数为2

import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.ListIterator;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class Main { 
        private int count;//记录需要的台数
        private int max;//记录需要单次拦截导弹数量最大值
        private int[] src;
        public Main(int[] src) {
            this.src = src;
            count = 0;
            max = Integer.MIN_VALUE;
            compute();
        }
        public int getCount() {
            return this.count;
        }
        public int getMax() {
            return this.max;
        }
        /** * 对于一个集合，求得该集合单次拦截导弹最大个数的最优解 * @param stack 被求解的导弹高度集合 * @return 获得的最优解的高度集合 */
        public static int[] result(Stack<Integer> stack) {
            LinkedList<int[]> resv = new LinkedList<int[]>();
            if(stack.isEmpty()) 
                return new int[0];
            //先初始化结果集合，将最后一个元素装入
            resv.add(new int[]{stack.pop()});
            while(!stack.isEmpty()) {
                int d = stack.pop();
                ListIterator<int[]> it = resv.listIterator();
                int[] last = it.next();
                //若当前数据比所有解的最大值都小，则更新最小解
                //i = 0
                if(d < last[0]) {
                    last[0] = d;
                    continue;
                }
                int[] next = last;
                //i > 0 && i < len
                while(it.hasNext()) {
                    next = it.next();
                    int llen = last.length;
                    int nlen = next.length;
                    //注：int数组里面的数据是升序排列，所以array[length - 1] 即为该数组的最大值
                    //若当前数据d大于前一项的最大值（说明可以在其后面插入）
                    //并且小于当前项的最大值（说明该解比当前解更优），则替换当前解为更优解
                    if(d > last[llen - 1] && d < next[nlen - 1]) {
                        int[] temp = new int[nlen];
                        for(int i = 0; i < llen; i++)
                            temp[i] = last[i];
                        temp[nlen - 1] = d;
                        it.set(temp);
                    }
                    last = next;
                }
                //若当前数据d大于所有解的最大值，则添加新的解
                //i > len
                if(d > next[next.length - 1]) {
                    int[] temp = new int[next.length + 1];
                    for(int i = 0; i < next.length; i++)
                        temp[i] = next[i];
                    temp[temp.length - 1] = d;
                    resv.add(temp);
                }
            }
            return resv.pollLast();
        }
        /** * 求src - minuend的差集，并将结果集合按照src原来的顺序装入stack中 * 例如 src = 389 207 155 300 299 170 65 * 而 minuend = 65 158 170 299 300 389 * 则 return stack = 207 155 * @param src * @param minuend * @return */
        private Stack<Integer> rest(int[] src,int[] minuend){
            Stack<Integer> stack = new Stack<Integer>();
            int i = 0, j = minuend.length - 1;
            while(i < src.length && j >= 0) {
                if(src[i] == minuend[j]) {
                    i++;
                    j--;
                }else {
                    stack.push(src[i]);
                    i++;
                }
            }
            while(i < src.length) {
                stack.push(src[i++]);
            }
            return stack;
        }
        /** * 将int数组转化为stack，出栈时逆向输出int数组数据 * @param data * @return */
        private Stack<Integer> convert2stack(int[] data){
            Stack<Integer> stack = new Stack<Integer>();
            for(int i : data)
                stack.push(i);
            return stack;
        }
        /** * 算法开始 */
        private void compute() {
            int[] temp = src;
            Stack<Integer> stack = convert2stack(this.src);
            while(!stack.isEmpty()) {
                int[] res = Main.result(stack);
                //若有更大的导弹数量则更新最大值
                if(max < res.length)
                    max = res.length;
                count++;//完成一次拦截，记录数+1
                stack = rest(temp,res);//将已经被拦截的导弹移除，并将剩余的导弹高度装入栈中
                //拷贝stack内的数据到src数组中
                temp = new int[stack.size()];
                int i = 0;
                for(int x : stack) {
                    temp[i++] = x;
                }
            }
        }
        public static void main(String[] args){
            LinkedList<Integer> list = new LinkedList<Integer>();
            //若本地测试输入，请从文件读入，否则无法终止输入
            //Scanner scan = new Scanner(new FileInputStream("D:\\test.txt"));
            Scanner scan = new Scanner(System.in);
            while(scan.hasNext()) {
                list.add(scan.nextInt());
            }
            scan.close();
    
            //由于不知道数据长度，所以先用了链表存储，然后再把数据拷贝到数组中
            //办法比较笨，如果有更好的办法请留言
            int[] src = new int[list.size()];
            int i = 0;
            for(Iterator<Integer> it = list.iterator();it.hasNext();) {
                src[i++] = it.next();
            }
    
            //算法开始
            Main t = new Main(src);
            System.out.println(t.getMax());
            System.out.println(t.getCount());
        }
    }

[http_www.stdal.com_archives_118]: http://www.stdal.com/archives/118
[SouthEast]: /images/20220601/319d6ec751594a72aa50164aa1c68af1.png
[1516944748690565.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516944748690565.png
[1516945168850410.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516945168850410.png
[1516945430308910.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516945430308910.png
[1516945657855049.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516945657855049.png
[1516945679899534.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516945679899534.png
[1516945862220403.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516945862220403.png
[1516945969569348.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516945969569348.png
[1516946088860765.png]: http://p2qpvn0jh.bkt.clouddn.com/wp-content/uploads/image/20180126/1516946088860765.png