M_sea

BZOJ2457 [BeiJing2011]双端队列
BZOJ分析正着很难想。正难则反,考虑反着做。已知一个非降序列,将其分成尽量少的几段,使得每一段对应一个合法的双端...
扫描右侧二维码阅读全文
03
2018/12

BZOJ2457 [BeiJing2011]双端队列

BZOJ

分析

正着很难想。正难则反,考虑反着做。

已知一个非降序列,将其分成尽量少的几段,使得每一段对应一个合法的双端队列。

然后发现一个合法的双端队列,一定满足下标先递减再递增。

然后就可以先sort,再贪心地凑。

对于相同的数,它们的顺序是可以交换的。显然下标递增或递减时最优。

然后就可以按照相同的数去划,每一个区间往后放,尽量的使得这样的单谷区间少。

举一个样例的例子:

$$A=[[0],[3,3],[6,6],[9]],B=[[3],[1,6],[2,5],4]]$$

先接$[0]$,下标变成$[3]$;然后接$[3,3]$,下标无法再递减,变成$[3,1,6]$;接$[6,6]$,下标无法再递增,变成$[3,1,6,5,2]$;最后接$[9]$,无法再递减,变成$[3,1,6,5,2,4]$。共有两个单谷段,答案为2。

可以每次开始递减时就ans++

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=200000+10;

struct node {
    int val,pos;
    bool operator <(const node& rhs) const {
        return (val<rhs.val)||((val==rhs.val)&&(pos<rhs.pos));
    }
};

node a[MAXN];
int Min[MAXN],Max[MAXN];

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) a[i].val=read(),a[i].pos=i;
    sort(a+1,a+n+1);
    int cnt=0;
    for (re int i=1;i<=n;++i)
        if (a[i].val!=a[i-1].val||i==1)
            Max[cnt]=a[i-1].pos,Min[++cnt]=a[i].pos;
    Max[cnt]=a[n].pos;
    int ans=1,last=Min[1],flag=0; //flag为0则递减,1则递增
    //这里ans=1是考虑第一段,是一个递减区间。
    for (re int i=2;i<=cnt;++i) {
        if (!flag) {
            if (last<Max[i]) flag=1,last=Max[i];
            else last=Min[i];
        }
        else {
            if (last>Min[i]) ++ans,flag=0,last=Min[i];
            else last=Max[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 03 日 10 : 16 PM

发表评论