洛谷OJ1020 nlogn解决最长非递增子序列与最长递增子序列
发布时间
阅读量：
阅读量
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是≤50000 \le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
111行，若干个整数（个数≤100000 \le 100000≤100000）
输出格式
222行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例
input:
389 207 155 300 299 170 158 65
output:
6
2
第一问可以转化为求最长非递增子序列,开一个vector,这个vector需要保证元素是非递增的.把第一个元素push进去,然后遍历从第二个开始的所有元素,如果这个新元素比vector最后一个元素要小,那么就加入vector,否则就找到vector里第一个小于heights[i]的元素,用heights[i]来替代这个元素,从而更新这个非递增子序列.注意的是lower_bound与upper_bound默认的比较函数是>,即默认的是找到比某元素大的元素,因此要传入comparator greater
第二问可以转化为最长递增子序列,对于每一个新传入的元素,如果新元素比序列最后一个元素要大,那么就添加进来,否则就找到第一个大于等于新元素的元素,替换它,以此来更新这个最长递增子序列.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> heights;
int height;
while(cin>>height) {
heights.push_back(height);
}
int size = heights.size();
vector<int> lnis;
lnis.push_back(heights[0]);
for(int i = 1; i < size; i++) {
if(heights[i] < =lnis.back()) { //非递减,等于号也可以
lnis.push_back(heights[i]);
}else{
*upper_bound(lnis.begin(), lnis.end(),heights[i], greater<int>()) = heights[i];
}
}
cout<<lnis.size()<<endl;
vector<int>lis;
lis.push_back(heights[0]);
for(int i = 1; i < size; i++) {
if(heights[i] > lis.back()){
lis.push_back(heights[i]);
}else {
*lower_bound(lis.begin(), lis.end(),heights[i]) = heights[i];
}
}
cout<<lis.size()<<endl;
}
全部评论 (0)
还没有任何评论哟~