BZOJ2457 双端队列

题解 算法-排序
题目链接 编辑文章

题意

需要用双端队列实现 $N$ 个数的排序。依次处理每一个数,每次只能将数放在队首或队尾,或新建一个队列。求需要的最少双端队列数。

$N\le 200000$ 。

题解

将原数列排序,可以得到 新数列对应原序列下标 的序列。如:

原序列下标序列
$[3,6,0,9,6,3]$$[1,2,3,4,5,6]$
$[0,3,3,6,6,9]$$[3,1,6,2,5,4]$

可以发现只有下标序列的一段满足先递减再递增(单谷),才能用一个双端队列实现。因为最小的数先处理,然后才能处理左右序号比它大的数。

不过原序列中相同的数对应的下标序列中的数可以交换位置,使得答案更优。如将 $[2,5]$ 交换位置可以只用 $2$ 个队列,若不交换则需要 $3$ 个。考虑贪心使得当前尽量形成单谷。

排序时用下标作为第二关键字,对于排序好的序列,记录相同的值的起点 $st$ 和终点 $ed$ ,显然两者分别为下标最小和最大值。

然后遍历每一个值,记录之间序列中最后一个下标 $last$ 和 序列状态 $flag$ ($0$ 表示递减,反之递增),作如下分类讨论:

  1. 序列递减且 $ed[i]>last$ ,没法继续单调递减,只有单调递增,更新 $last=ed[i]$
  2. 序列递增且 $st[i]<last$ ,没法继续递增,改为单调递减,同时 $ans++$ ,更新 $last=ed[i]$
  3. 否则继续递减或递增
#include<bits/stdc++.h>

using namespace std;

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

struct node {
    int s,id;
} s[200005];
int n,cnt,st[200005],ed[200005];

inline bool cmp(const node &x,const node &y) { return x.s==y.s ? x.id<y.id : x.s<y.s; }

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].s=read(),s[i].id=i;
    sort(s+1,s+n+1,cmp);
    st[++cnt]=s[1].id;
    for (int i=2;i<=n;i++)
    {
        if (s[i].s==s[i-1].s) continue;
        ed[cnt]=s[i-1].id;
        st[++cnt]=s[i].id;
    }
    ed[cnt]=s[n].id;
    int last=st[1],ans=1; bool now=0;
    for (int i=2;i<=cnt;i++)
    {
        if (!now && ed[i]>last) now=1;
        else if (now && st[i]<last) ans++,now=0;
        last=now ? ed[i] : st[i];
    }
    return !printf("%d",ans);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。