(压行狂魔)
蒟蒻第一次发题解,请谅解x(原来标题要发完才能改的么)
具体的贪心法也有dalao说了,我们来看代码实现
首先用一个编号排序得到了id数组,表示排序后每个数对应原来的编号
然后进行缩点操作,用b数组(代表block的意思)记录相等数组成段的左右端点,排序后段内的编号一定是单调递增的
接下来模拟双端队列的操作,依次将段插入序列,delta=1表示递减插入,反之为递增
初始化为递减(递增一定不会更优)
序列递减时,如果当前段的右端点大于前一段的左端点,则新一段递增插入,此时双端队列数ans+1
反之如果当前段的左端点小于前一段的右端点,则递减插入
可以用一个异或判断语句来表示,满足条件delta取反
(讲的一点不清楚,应该没人看到吧)
C++ 代码
#include<bits/stdc++.h>
#define N 200009
using namespace std;
int n,x[N],id[N],b[N][2],cnt,ans;
bool cmp(const int&a,const int&b){return x[a]<x[b]||x[a]==x[b]&&a<b;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&x[id[i]=i]);
sort(id+1,id+n+1,cmp);
for(int i=1;i<=n;i++)
if(x[id[i]]!=x[id[i-1]])b[++cnt][0]=id[i],b[cnt-1][1]=id[i-1];
b[cnt][1]=id[n];
for(int i=1,delta=0;i<=cnt;i++)
if(i==1||delta^b[i][delta]<b[i-1][!delta])ans+=delta=!delta;
cout<<ans<<endl;
return 0;
}
%%% tql!!!