题解 P3902 【递增】

The_Key · 2017-08-11 15:56:30 · 题解

作为本题的第一篇题解，本蒟蒻表示很鸡冻o(*￣▽￣*)o

在此介绍一种奇门遁甲之术——STL中的 lower_bound()函数

lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个不小于value 的值——引自百度百科（个人口才太差解释不清。。）

这题可以边输入边判断，用lower_bound()函数取地址然后赋值同时累加器计数，最后输出累加器的值就是最终结果

#include<iostream>
#include<algorithm>
using namespace std;
long long n,num,now,sum,f[1001];
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>num;
        if(num>f[now])//如果这个数比以前的大说明不破坏数列严格递增的性质那么将这个数放在数列都后面
        f[++now]=num;
        else
        {
            *lower_bound(f+1,f+now+1,num)=num;//如果这个数比之前的数小那么用lower_bound()函数找到它适合的位置将这个数放进去
            sum++;//这样做相当于修改一个数，所以累加器加1
        }
    }
    cout<<sum;
    return 0;
}
//比人代码不精大神勿喷