[模板] Java实现upper_bound(), lower_bound() & 最长(不)上升序列长度与数量 （蓝桥杯经典算法 导弹拦截）

Java实现upper_bound(), lower_bound()

蓝桥杯算法教学与培训 蓝桥杯培训内部讲解 导弹拦截

蓝桥杯练习系统 试题 算法训练 拦截导弹

P1020 导弹拦截 - 洛谷 | 计算机科学教育新生态

€€£ NOIP经典老题

资源限制

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

问题描述

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

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

输入格式

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

输出格式

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

思路

先抛概念：

  最长上升子序列，指一个序列中最长的单调递增的子序列。

  那剩下的都差不多了…只差一个大于(等于)/小于(等于)号的事。

求『最多能拦截的导弹数』的过程：

  即计算最长不上升子序列的长度

  假设该有序队列现态a[]={a0,a1,a2…am},现将数x加入队列，若有x>=a[m]，那么直接令a[m+1]=x即可；否则寻找a[i]<x<a[i+1]，将x与a[i+1]进行替换。

  这个过程也导致了该方法只能求出序列长度，a[]并不是所求最长序列…

  维护『要拦截所有导弹最少要配备的系统数』
(最长不上升子序列的数量)即是求出这个系统中最长上升序列长度。

证明参考：DP-导弹拦截 - JJPJJ的博客 - 洛谷博客

2、对于问二求整个数列的最长上升子序列即可。证明如下：

（1）假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。

（2）假设我们得到了最小划分的K组导弹，从第 a (1<=a<=K) 组导弹中任取一个导弹，必定可以从 a+1 组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比a+1组中任意一个导更高，在打第 a 组时应该会把 a+1 组所有导弹一起打下而不是另归为第 a+1 组），同样从 a+1 组到 a+2 组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来，连成一条上升子序列，其长度即为 K ;

（3）设最长上升子序列长度为P，则有 K<=P ;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升)，则有 P>=K ，所以 K=P 。

//c++ --std==c++11
#include <cstdio>
#include <algorithm>//lower_bound,upper_bound
#include <queue>//greater<>()

using namespace std;

const int MAXN = 100000 + 5;

int src[MAXN], q[MAXN], l[MAXN];
//src为原数组，q是每个不上升子序列的末尾元素值，l用来维护最长不上升子序列长度
int con = 1, cont = 1, n;

int main(){
    while (scanf("%d", &src[++n]) != EOF);
    --n; q[1] = src[1]; l[1] = src[1];
    for (int i = 2; i <= n; ++i){
        /*****求最长队列与求队列数量部分没有直接联系******/
        if (l[cont] >= src[i])  //维护最长队列
            l[++cont] = src[i]; //如果当前元素小于等于队列尾元素则直接加到队列尾
        else
            *upper_bound(l + 1, l + cont + 1, src[i], greater<int>()) = src[i]; //否则替换第一个小于这个元素的位置
        //**！！程序运行完后L队列并非最长不下降子序列！！该方法仅能求序列长度！！**//
        if (q[con] < src[i])   //处理末尾队列
            q[++con] = src[i]; //如果加不到之前任何一个队列上，新开一个队列
        else
            *lower_bound(q + 1, q + con + 1, src[i]) = src[i]; //否则把这个元素加到末尾大的最少的队列上
    }
    printf("%d\n%d", cont, con);
    return 0;
}

//java
import java.util.*;
import java.math.*;

public class Main {
	
	public static int lowerBound(int[] args, int begin, int end, int value) {
		while (begin < end) {
			int mid = begin + (end - begin) / 2;
			if (args[mid] < value) {
				begin = mid + 1;
			} else {
				end = mid;
			}
		}
		return begin;
	}

	public static int upperBoundGreater(int[] args, int begin, int end, int value) {
		while (begin < end) {
			int mid = begin + (end - begin) / 2;
			if (args[mid] >= value) {
				begin = mid+1;
			} else {
				end = mid;
			}
		}
		return begin;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int con = 1, cont = 1, n = 0;
		String[] s = sc.nextLine().split(" ");
		int src[] = new int[s.length+1],
			q[] = new int[s.length+1],
			l[] = new int[s.length+1];
		//src为原数组，q是每个不上升子序列的末尾元素值，l用来维护最长不上升子序列长度
		for (int i = 1; i <= s.length; i++)
			src[i] = Integer.parseInt(s[i-1]);
		n=s.length;
		q[1] = src[1];
		l[1] = src[1];
		for (int i = 2; i <= n; ++i) {
			/***** 求最长队列与求队列数量部分没有直接联系 ******/
			if (l[cont] >= src[i]) // 维护最长队列
				l[++cont] = src[i]; // 如果当前元素小于等于队列尾元素则直接加到队列尾
			else {
				int it = upperBoundGreater(l, 1, cont + 1, src[i]);
				l[it] = src[i]; // 否则替换第一个小于这个元素的位置
			}
			// **！！程序运行完后L队列并非最长不下降子序列！！该方法仅能求序列长度！！**//
			if (q[con] < src[i]) // 处理末尾队列
				q[++con] = src[i]; // 如果加不到之前任何一个队列上，新开一个队列
			else {
				int it = lowerBound(q, 1, con + 1, src[i]);
				q[it] = src[i];// 否则把这个元素加到末尾大的最少的队列上
			}
		}
		System.out.printf("%d\n%d", cont, con);
	}
}

不得不说一下c++的stl是真的强大啊…