• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P1020 [NOIP1999 普及组] 导弹拦截(此题的时间复杂度为n*logn,求最长的(上升或下降)序列)应作为模板使用

开发技术 开发技术 2周前 (04-08) 4次浏览
这道题,没理解透彻,对于题解中,查找最长升序序列,和最长降序序列的方法还没完全理解
题目就是找一个最长升序序列,为至少要的导弹拦截布置数,降序序列为最多的拦截导弹数
#include <bits/stdc++.h> using namespace std; #define ll long long const int M = 1e5 + 1; int f1[M], f2[M], a[M];//f1为降序,f2为升序 int main() { int n = 0; while (scanf("%d", &a[++n]) != EOF); n--;//这里也不太懂为何要-1 int len1 = 1, len2 = 1; f1[1] = a[1];//初始状态都是先拿了a数组中的第一个元素 f2[1] = a[1]; for (int i = 2; i <= n; i++) { if (f1[len1] >= a[i]) f1[++len1] = a[i];//求下降的序列 else {
       //通过upper_bound来查找第一个小于他的数,注意后面加了greater<int>(),把它踢出去
int p = upper_bound(f1 + 1, f1 + 1 + len1, a[i],greater<int>())-f1; f1[p] = a[i]; } if (f2[len2] < a[i]) f2[++len2] = a[i];//求上升的序列 else { int p = lower_bound(f2 + 1, f2 + 1 + len2, a[i])-f2;//注意这里用lower_bound找 f2[p] = a[i]; } } cout << len1 << endl << len2 << endl; return 0; }

 


喜欢 (0)