题解 P1020 【导弹拦截】

做这道题的时候看了很多题解，也没看懂，各种查终于弄明白了O(nlogn)的方法，自己来写一篇，试试能不能让更多人知道QwQ 注：树状数组做法请去别的大佬那里看，树状数组还是挺重要的。 这道题的做法很多，别的dalao题解里都有 dalao们也说了，根据"xxxx定理"，这题只需要求一个**不上升序列长度**和一个**上升序列长度** 我只说说如何找出它们的长度 写给萌新看，求dalao们轻喷(>﹏<) (如果有锅请dalao们指出) ## 一、lower_bound与upper_bound zhx曾经曰过，STL很慢 hja曾经曰过，觉得STL慢是以zhx为首的一批oi选手的偏见 我们不管他们曰过什么，只来看看这两个函数 ### 1.作用 这两个是STL中的函数，作用很相似： 假设我们查找x，那么： lower_bound会找出序列中第一个**大于等于**x的数 upper_bound会找出序列中第一个**大于**x的数 没错这俩就差个**等于**号╮(╯▽╰)╭ ### 2.用法 以下都以lower_bound做栗子 (因为upper_bound做出的栗子不好吃) (~~其实就是我懒得打两遍~~) 它们俩使用的前提是一样的：序列是**有序**的 对于一个数组a，在[1,n]的区间内查找**大于等于**x的数(假设那个数是y)，函数就写成： ```cpp lower_bound(a + 1, a + 1 + n, x); ``` 函数返回一个指向y的指针 看着是不是很熟悉？回想`sort`使用的时候： ```cpp sort(a, a + 1 + n, cmp); ``` 这里`a+1,a+1+n`的写法是不是很像？ STL里面的函数写区间一般都这个尿性 同样的，`lower_bound`和`upper_bound`也是可以加**比较函数**`cmp`的： ```cpp lower_bound(a + 1, a + 1 + n, x, cmp); ``` 到这里不得不说说前面的"**有序**序列"，这里的"**有序**"是对什么有序？ 你可能已经猜到了，它是对于比较器有序，并且必须是**升序**！ (为什么不是降序？这个你可能要去问问写STL的人) 一旦对降序序列使用`lower_bound`，就会出现神奇的错误，具体原因可以看这篇： https://blog.csdn.net/qq1337715208/article/details/81072709 当然比较器默认也是"**＜**" 如果要在一个**下降**序列里寻找一个**小于**x的数呢？ 根据我们之前说的，`lower_bound`只能对上升序列使用，那我假装**下降序列**是个**上升序列**就行了嘛～ (lower_bound：你当我傻吗)(w1049：没错我就当你傻) 只需要把比较器改成"**>**"： ```cpp lower_bound(a + 1, a + 1 + n, x, cmp); ``` 同时需要写一个函数`cmp`： ```cpp bool cmp(const int& a,const int& b){return a > b;} ``` 当然，你也可以这样： ```cpp lower_bound(a + 1, a + 1 + n, x, greater <int> () ); ``` 这里的**greater<int>()**就是c++友情提供的方便的大于函数，这样就不用自己动手写一个cmp函数了(~~其实就是懒~~) 它们的实现方式是二分查找 ，存在的意义就是让我们写代码更方便~~地偷懒~~(一行lower_bound比写二分查找方便多了) ### 3.返回值 众所周知，~~小葱非常擅长计算组合数~~返回的是个**指针** 对于返回值我们有两种处理方式： ###### 第一种： 许多人讨厌指针，那么我们用这个指针**减去**数组开头的指针(即**数组名**)，得到两个指针的差，就是**数组下标**，即： ```cpp int p = lower_bound(懒得写) - a; ``` 那么a[p]就是要找的y (如果不知道为什么就记着好了) ##### 第二种： 指针好！指针秒！ 改革春风吹满地，用指针的oier真争气！ (以上两行你可以当做什么都没看见) ```cpp int *p = lower_bound(还是懒得写); ``` 那么*p就是要找的y ~~可以看出指针多么直接，不像数组下标还要倒腾一遍~~ #### 总结一下：#### 好像没什么可总结的QwQ 对一个**下降**序列a ```cpp int p = lower_bound(a + 1, a + 1 + n, x, greater <int> () ) - a; ``` a[p]即a[1]到a[n]中第一个小于等于x的数 (被遗忘的upper_bound表示不服) ## 二、O(nlogn)求出最长不上升子序列的长度 (即**一套系统最多拦截数**)(~~终于到二了~~) ### 1.实现方式 首先我们需要一个数组**a**，存储从第1个到第n个导弹的高度 然后一个数组**d**(其实是个栈)，存储不上升序列 把a中的**每个元素**挨个加到d里面： (a中第i个元素为a[i]，d长度为len，d中最后一个(也是最小的一个)为d[len]) #### 如果a[i] <= d[len]，说明a[i]可以接在d后面(而整个d还是有序的)，那就简单粗暴地把a[i]丟进d： ```cpp d[++len] = a[i] ``` #### 如果a[i] > d[len]，说明a[i]接不上 但是我们发扬**瞎搞精神**：**接的上要接，接不上创造条件也要接！** ###### 强行把a[i]塞进去： 在d中找到**第一个小于**a[i]的数，把它**踹了**，用a[i]**代替**它！(为什么正确在下面） 假设这个数是y，怎样踹掉它呢？ 很明显，我们需要使用lower_bound和upper_bound来查找 **第一步，找一个听起来无比正确的理由**，比如它占着位置不干活啦，干起活来还不如a[i]啦，naive啦，它too young啦，too simple啦......反正能骗过lower_bound和upper_bound就行 (lower_bound&&upper_bound：你当我们傻)(w1049：真聪明) 接下来，特别有正义感的lower_bound和upper_bound就会去把y给拎出来 **第二步，考虑使用什么** 我们知道，要求的是最大**不上升**子序列长度，也就是如果两个元素**相等也是可以**的 所以我们踹人就**不用踹等于a[i]的**了 结合上面，应该使用**upper_bound**(终于想起来它了)并且**使用>作为比较器**(这是个下降序列) **第三步，直接开搞** ```cpp int p = upper_bound(d + 1, d + 1 + len, a[i], greater<int>()) - d; d[p] = a[i]; ``` 成功把a[i]塞了进去 ### 2.为什么正确 ~~显然成立~~ 如果y**在**末尾，由于y < a[i]，所以**y后面能接的不如a[i]多**，y让位给a[i]可以让序列更长 如果y**不在**末尾，那y有生之年都**不会再被用到**了，直接踹了y就行，y咋样，**who care？** 注意到lower_bound只能在**有序**序列中使用，此时d还有序吗？ **当然有序**。(本文第一个句号) 假设y前一个y1，y后一个是y2，则 $y1 > y > y2$ 因为y是第一个小于a[i]的，所以 $y1 > a[i]$ 又因为 $a[i] > y > y2$ 所以 $y1 > $**a[i]**$ > y2$ 对比下原来的式子 $y1 > $**y**$ > y2$ a[i]可以完美代替y，至于y以后咋办，**who care？** 对于**最长上升子序列**，只需要把上面的过程通通**换一下符号** 可以用以下方法证明： ```cpp 反之亦然同理，推论自然成立，略去过程QED，由上可知证毕(多么美妙的证明) ``` 实际上，$d[i]$的含义是：最大不上升子序列长度为$i$时，最优的结尾元素。 ### 3.代码： ```cpp for(int i=2;i<=n;i++) if(d[len]>=a[i])d[++len]=a[i]; else { int p=upper_bound(d+1,d+1+len,a[i],greater<int>())-d; d[p]=a[i]; } ``` 最后len就是要求的最大不上升子序列**长度** 但要注意的是，d中存储的**并不是**最大不上升子序列！ 原因如下： ```cpp 即得易见平凡，仿照上例显然，留作习题答案略，读者自证不难 ``` ### 4.对样例模拟： ~~在这里推荐一下DevC++的调试器(不用DevC++的当我没说)~~ （还是不要推荐了） 1.我们把a[i]**(389)**加入d：  2.**i=2**，此时a[i]**(207)**<=d[len]**(389)**，把a[2]加入d：  3.**i=3**，此时a[i]**(155)**<=d[len]**(207)**，把a[3]加入d：  4.**i=4**，此时a[i]**(300)**>d[len]**(155)**，不能直接加入，所以准备踹人  5.找出d中第一个小于a[i]**(300)**的(即**207**)，用a[i]换掉  6.**i=5**，此时a[i]**(299)**>d[len]**(155)**，不能直接加入，所以准备踹人  7.找出d中第一个小于a[i]**(299)**的(即**155**)，用a[i]换掉  8.**i=6**，此时a[i]**(170)**<=d[len]**(299)**，把a[6]加入d：  9.**i=7**，此时a[i]**(158)**<=d[len]**(170)**，把a[7]加入d：  10.**i=8**，此时a[i]**(65)**<=d[len]**(158)**，把a[8]加入d：  **至此**，得到最大不上升子序列长度**len=6** ## 三、AC代码： ```cpp #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int a[N], d1[N], d2[N], n; int main() { while (cin >> a[++n]); n--; //输入 int len1 = 1, len2 = 1; //初始长度为1 d1[1] = a[1]; //用于求不上升序列长度 d2[1] = a[1]; //用于求上升序列长度 for (int i=2; i<=n; i++) { //从a[2]开始枚举每个数(a[1]已经加进去了) if (d1[len1] >= a[i]) d1[++len1] = a[i]; //如果满足要求(不上升)就加入d1 else { //否则用a[i]替换d1中的一个数 int p1 = upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) - d1; d1[p1] = a[i]; } if (d2[len2] < a[i]) d2[++len2] = a[i]; //同上 else { int p2 = lower_bound(d2 + 1, d2 + 1 + len2, a[i]) - d2; d2[p2] = a[i]; } } cout << len1 << endl << len2; //输出 return 0; //结束 } ``` 更快速的版本： ```cpp #include<iostream> #include<cstdio> #include<algorithm> #define R register using namespace std; const int N=100010; int a[N],d1[N],d2[N],n; inline bool read(int &x) { char c=getchar(); if(c==EOF)return false; while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return true; } int main() { while(read(a[++n]));n--; R int len1=1,len2=1; d1[1]=d2[1]=a[1]; for(R int i=2; i<=n; i++) { if(d1[len1]>=a[i])d1[++len1]=a[i]; else *upper_bound(d1+1,d1+1+len1,a[i],greater<int>())=a[i]; if(d2[len2]<a[i])d2[++len2]=a[i]; else *lower_bound(d2+1,d2+1+len2,a[i])=a[i]; } printf("%d\n%d",len1,len2); return 0; } ``` 一年过去，百感交集，虽然已经凉了，但是还是改正了一下这篇我唯一写的还行的题解里面的错误，祝各位在复活的NOIP中取得好成绩。 原来的代码`return 0；`中有个中文分号，现在已经没了。