蓝桥杯算法训练 拦截导弹 ByAssassin[最长下降子序列nlogn]

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

思路：非常明显而且经典的最长下降子序列的题目，题目中又说明了每个数值大小不同更是降低了难度。 题目要求分为两部分： 1.求最长下降子序列 2.求需要几串下降的子序列才能包含全串

问题一 ：求最长下降子序列

因为我们在题目中看到数值不超过30000那么通常的dp用O（N^2）的方法是会超时的！那么我们需要优化一下。思路就是贪心+二分查找

求一个序列的最长上升子序列，可以用贪心的思想来做。

例：389 207 155 300 299 170 158 65

要求它的最长递减子序列，具体步骤如下：

389

389 207

389 207 155

389 300 155 //207被300替换了，207是三个数中刚好小于300的数，207能接的后序列，300照样能接，而且有更大的空间可以接

389 300 299 //此次用299替换155，一样是因为有更大的空间可用，在这里就体现了用300来替换207的正确性

389 300 299 170

389 300 299 170 158

389 300 299 170 158 65

这样就得到了一个最长递减子序列，而且更有可能接更多的数 最后这个串的长度就是最大的长度！ 我们假定变化的数组为X，源数据数组为Y，那么假定Y[i]比X当前最小值还小，那么加到X的后面，否则二分查找X串中比Y[i]小的最大的值，并替换成Y[i]。具体如上！

问题二 ：求需要几串下降的子序列才能包含全串

事实上这个继续用贪心就可以了，但是需要结合队列用。 前提是我们要求队列数，假定一个下降子序列为一队，只要一队一队去掉，然后统计有几队即可！而且，不需要每一队是最优的！因为只要出现一个值比前一个值大（顺序对），那么就必须再有一个队，比如说 8 7 6 3 5 4 2 1 那么一定是2队，可以使8 7 6 3 2 1+5 4（5比前面的3大） 并不需要是每队最优的。（说不太清，自己体会一下吧） 那么实现的时候我们可以用队列，每一轮摘取出一队，递减的数直接pop掉，出现比前面大的情况就压到队列的尾部。知道所有的队都被提取了出来！ 哎，说不太清,直接看代码吧…5_5

#include<bits/stdc++.h> using namespace std; int value[30001],length=0; int getmax[30001],maxlength,maxpos; //maxlength表示下降子序列的最大长度 ，讲解中的X串 void dfs(int start,int end,int temp){ //二分查找 if(start>end) return; int mid=(start+end)/2; if(getmax[mid]<temp){ maxpos=mid; //比Y[i]小的最大的值的位置 dfs(start,mid-1,temp); //继续向前搜索 } else{ dfs(mid+1,end,temp); } } int main(){ //freopen("input.txt","r",stdin); while(scanf("%d",&value[++length])!=EOF); //输入，真实的长度为length-1，自己试一下 getmax[1]=value[1]; maxlength=1; for(int i=2;i<length;i++){ if(value[i]<getmax[maxlength]){ //如果Y[i]比X当前最小值还小 getmax[++maxlength]=value[i]; //那么Y[i]加到X的后面 } else{ dfs(1,maxlength,value[i]); //否则二分查找X串中比Y[i]小的最大的值，并替换成Y[i] getmax[maxpos]=value[i]; } } cout<<maxlength<<endl; length--; //更正length Y的长度 queue<int>q; //用队列实现lines数的统计 int lines=0,maxtemp,len; // maxtemp代表每队当前的最小值 for(int i=1;i<=length;i++){ q.push(value[i]); } while(!q.empty()){ maxtemp=q.front(); len=length; //每次初始化当前queue的长度 for(int t=1;t<=len;t++){ if(q.front()<=maxtemp){ maxtemp=q.front(); q.pop(); length--; //更新length长度 } else{ q.push(q.front()); //如果出现顺序对那么压回队列 q.pop(); } } lines++; //统计队数 } cout<<lines<<endl; return 0; }