题目描述
分析:
第一种方法有操作冗余:
如果a2 《 a1,那么a2 比a1的更合适,序列长度可能更大
那么每次都无需考虑a1的情况。
因此序列中的每个元素是以其结尾的构成上升子序列的最小元素。
更新题解:
每次更新的时候都使用二分法,找到略小于(不能等于)a[i]的值的下标k,把a[i]更新成k+1位置的元素。
例如:
流程:
流程:
q存放上升子序列
a原始序列 len序列长度
1.输入a数组
2.迭代n(I : 0 ~ n - 1)次:
当时写的有差错,已更新
二分法在f中 找到 < a[i]的最大值,跳出二分的时候r = 当前数下标。
3.把当前数加入到f序列中,len = max(len, r + 1), 添加或者替换的元素 f[r + 1] = a[i]
模拟:
记录的错误:
PS:
总结二分:
二分的两种模板都可行,都能求x的左右边界。而决定求x的左边接的是
1.q[mid] > x(求大于x的最小值), q[mid] >= x(求>= x 的最小值,有x就是x,没有x就相当于前一种)
2.q[mid] < x (求小于x的最大值) 类比上面……
算法1
(二分+贪心) $O(NlogN)$
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int f[N], a[N], n;
void bid()
{
int len = 1;
for(int i = 1; i <= n; ++i)
{
int l = 1, r = len;
while(l < r)
{
int mid = l + r + 1>> 1;
if(f[mid] < a[i])l = mid;
else r = mid - 1;
}
len = max(r + 1, len);
f[r + 1] = a[i];
}
cout << len - 1<< endl;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
}
bid();
return 0;
}
写的很清楚,我的疑惑在这里解开了,谢谢~
谢谢~