算法模拟+二分优化
时间复杂度O(nlogn)
这道题本身并不难QAQ但在二分上我出了问题
首先你需要证明num中的序列一定是个单调递增的序列,所以才能二分去找第一个大于或等于x的数
但在使用二分时出了问题,关于lower_bround and upper_bround的使用
1.lower_bound 返回的是第一个大于或等于x的数的位置
2.upper_bound 返回的时第一个大于x数的位置
这道题用这两个随便哪个都行
以lower_bound为例,lower_bound(1,2,3,4) 4个参数
1参为起始位置,2参为终止位置,3参为查询的数,4参为bool(可省)如果找大于的可省,找小于的要加bool函数
**注意**
这个函数返回值是一个迭代器,要得到位置可以(如下面代码内容所示)
C++ 代码
#include<bits/stdc++.h>
#define pb push_back
#define pp pop_back
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=100010,mod=1e9+7;
vector<int> num;
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(!i)
{
num.pb(x);
}
else
{
int j=lower_bound(num.begin(),num.end(),x)-num.begin();
if(j==num.size())
{
num.pb(x);
}
else
{
num[j]=x;
}
//cout<<j<<" "<<num[j]<<" "<<num.size()<<endl;
}
}
// for(int i=0;i<num.size();i++) cout<<num[i]<<endl;
cout<<num.size()<<endl;
return 0;
}