洛谷P1020 导弹拦截【单调栈】-白红宇

洛谷P1020 导弹拦截【单调栈】

阅读量：5289 次

发布时间：2019-06-14

本文共 1872 字，大约阅读时间需要 6 分钟。

题目：

题意：

给定一些导弹的高度。

一个导弹系统只能拦截高度不增的一系列导弹，问如果只有一个系统最多能拦截多少导弹。

再问，如果要拦截所有导弹最少需要多少系统。

思路：

对于第一个问题其实就是找整个序列中的最长不升子序列。

对于第二个问题就是找整个序列中的最长上升子序列。因为当有一个高度大于前面的高度时一个系统就搞定不了了。

最长上升子序列用动态规划是可以做的，但是这题会卡。

$O(N^2)$的动规做法是，$dp[i] = max(dp[i], dp[j] + 1),if height[i] > height[j]$

还有一种$O(NlogN)$的做法。这时我们维护一个单调栈。数是从小到大排序的，对于新的一个数，如果比栈顶的元素大，就直接加入栈中。

如果新的数比栈顶要小，我们就在栈中二分查找一个最小的大于新的数的数替换掉。

因为对于已经选好了的序列，我们替换前面的数的话并不会影响答案的长度。但是用更小的数替换大的数将有更大的机会让加入的数变多。

而二分找这样的数也非常简单，使用STL里的upper_bound()和lower_bound()就可以解决了。

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。

1 #include
     
       2 #include
      
        3 #include
        4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 13 #define inf 0x7fffffff14 using namespace std;15 typedef long long LL;16 typedef pair
                
                  pr;17 18 const int maxn = 1e5 + 5;19 int height[maxn];20 int n = 0;21 int incre[maxn], decre[maxn];22 int len1 = 0, len2 = 0;23 24 int main()25 {26 while(scanf("%d", &height[n++]) != EOF);27 for(int i = 0; i < n; i++){28 if(height[i] > incre[len1]){29 incre[++len1] = height[i];30 }31 else{32 int j = lower_bound(incre, incre + len1 + 1, height[i]) - incre;33 incre[j] = height[i];34 }35 36 if(height[i] <= decre[len2]){37 decre[++len2] = height[i];38 }39 else{40 int j = upper_bound(decre, decre + len2 + 1, height[i], greater
                 
                  () ) - decre;41 decre[j] = height[i];42 }43 }44 45 46 printf("%d\n%d\n", len2, len1);47 return 0; 48 }

转载于:https://www.cnblogs.com/wyboooo/p/10805027.html

你可能感兴趣的文章