AcWing 482. 合唱队形(二分)
原题链接
中等
作者:
dongdong
,
2021-02-01 12:21:59
,
所有人可见
,
阅读 263
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>dp1,dp2;
int n,num[N],ans1[N],ans2[N],ans;
int main()
{
cin>>n;
for(int i = 1;i <= n;i ++)
cin>>num[i];
dp1.push_back(num[1]);dp2.push_back(num[n]);
ans1[1] = ans2[n] = 1;
for(int i = 2;i <= n;i ++)
if(num[i] > dp1.back())
{
dp1.push_back(num[i]);
ans1[i] = dp1.size();
}
else
{
ans1[i] = lower_bound(dp1.begin(),dp1.end(),num[i]) - dp1.begin() + 1;
*lower_bound(dp1.begin(),dp1.end(),num[i]) = num[i];
}
for(int i = n - 1;i >= 1;i --)
if(num[i] > dp2.back())
{
dp2.push_back(num[i]);
ans2[i] = dp2.size();
}
else
{
ans2[i] = lower_bound(dp2.begin(),dp2.end(),num[i]) - dp2.begin() + 1;
*lower_bound(dp2.begin(),dp2.end(),num[i]) = num[i];
}
for(int i = 1;i <= n;i ++)
ans = max(ans,ans1[i] + ans2[i] - 1);
cout<<(n - ans);
}