CDOJ(UESTC) 251 导弹拦截（最长递增子序列nlogn算法+路径打印）

川长思鸟来 2024-02-17 20:28 4阅读 0赞

## 导弹拦截 ##

###### Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) ######

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹，同时，司令部想知道拦截下来的导弹的高度。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

### Input ###

第一行是一个整数*t*

,代表case数。对于每一个case，第一行是一个整数  *n*(1≤*n*≤100000)；第二行是  *n*个非负整数，表示第  *n*枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。数据保证高度不会超过  100000

### Output ###

对于每一个case,第一行输出最多能拦截的导弹数，第二行按来袭顺序输出拦截下来的导弹的高度构成的序列，以一个空格隔开。若有不止一种方法可以拦截最多的导弹，输出字典序最小的。

### Sample input and output ###

<table> 
 <thead> 
  <tr> 
   <th style="width:50%">Sample Input</th> 
   <th style="width:50%">Sample Output</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td> <pre>1
5
1 6 3 5 7</pre> </td> 
   <td> <pre>4
1 3 5 7</pre> </td> 
  </tr> 
 </tbody> 
</table>

分析：考察知识点：最长递增子序列的nlogn算法（用到了二分查找）+ 打印路径。如果不熟悉nlogn算法，可以访问 http://blog.csdn.net/u013806814/article/details/38711125 ，此题有一定的难度，看了别人的题解才知道了如何保存路径。

我们知道nlogn算法中有一个B\[len\]数组，表示长度为len的子序列对应的最小末尾（比如说子序列1,3,5和1,3,7, 此时最小末尾是B\[3\]=5，最长递增序列嘛，肯定是当长度相同时，末尾数越小越好）。

路径的记录：用num\[i\]来储存长度（最小末尾为d\[i\]的长度），关键来了，当LIS过了一遍之后，从后向前遍历（为什么呢？这是因为在执行nlogn的时候，同一长度len对应了多个最小末尾（因为i->n的过程中最小末尾不断更新：不同的i对应，但都被num\[i\]记录下来了））；很有意思的一道题，值得细嚼慢咽，比较靠思维。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=100000+10;
    int d[maxn]; //原序列 
    int B[maxn];  //LIS中用到的辅助序列 
    int path[maxn];  //打印路径序列 
    int num[maxn];//存储长度 (长度为len的最小末尾d[i]，通过下标i找到d[i])
    int n;
    
    int binary_search1(int first,int end,int tmp){  //二分查找 
    	int mid;
    	while(first<end){
    		mid=first+(end-first)/2;
    		if(B[mid]>=tmp) end=mid;
    		else first=mid+1;
    	}
    	return first;
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d",&n);
    		for(int i=1;i<=n;i++)
    		scanf("%d",&d[i]);
    		
    		int len = 1;
    		B[1]=d[1]; 
    		num[1]=1;
    		for(int i=2;i<=n;i++){
    			if(d[i]>B[len]){
    				B[++len]=d[i];
    				num[i]=len;
    			}
    			else {
    				int j=binary_search1(1,len,d[i]);
    				B[j]=d[i];
    				num[i]=j;
    			}
    		}
    		
    		int last=maxn,l1=len;
    		for(int i=n;i>=1;i--){
    			if(!l1)break;
    			if(num[i]==l1 && d[i]<last){
    				path[l1]=d[i];
    				last=d[i];
    				l1--;
    			}
        	}
    		
    	    printf("%d\n%d",len,path[1]);
    		for(int i=2;i<=len;i++){
    			printf(" %d",path[i]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

带上一组测试数据：

10  
2 2 3 10 6 1 2 3 4 5  
输出：

1 2 3 4 5