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

题目链接：

在做这个题的时候，首先要知道在STL中有可以实现二分查找的快速函数，常使用的有四种，分别是：

• lower_bound(): 找到大于等于某值第一次出现的迭代器位置；
• upper_bound():找到大于某值第一次出现的迭代器的位置；
• equal_range():z找到等于某值迭代器范围；
• binary_search(): 在有序序列中确定，给定元素是否存在；

这个题就是不断更新当前所在数组的最小值，如果输入的值，比当前元素的最大值大，数组就多添加一个数，如果比最大的值小，就使用二分查找，找到第一个大于这个值的元素的位置，并且更新这给位置的数组，使其为当前输入的数，最后统计数组的元素个数，就是要求的答案。

代码如下：

int n; int a[maxn];int main(){	ios::sync_with_stdio(false);	cin >> n;	int k;	int t = 0;	for(int i = 0; i < n; i++){		cin >> k;		if(i == 0) a[t++] = k;		else{			if(a[t-1] < k){				a[t++] = k;			}else{				int l = lower_bound(a,a+t,k)-a;				a[l] = k;				//cout << l << endl;			}		}	}	/*for(int i = 0; i < t-1; i++){		cout << a[i] << " ";	}	cout << a[t-1] << endl;*/	cout << t << endl;	return 0;}

转载地址：http://lqpfb.baihongyu.com/