题目描述

blablabla

样例

blablabla

算法1

我们知道，要满足题目要求的话。每个双端队列里面的序列一定是非降序的。当所有的双端队列合在一起的时候，也是非降序的。那么我们现在可以这样考虑，想象一下，每个双端队列的入队情况。下标最小的值入队，然后后面的数如果比他大 则放右边 反之，放左边。如此，那么这个双端队列的下标序列一定是先递减在递增的序列。称为单谷性质。

我们可以这样理解，一个双端队列能装一个单谷。当这个序列按有序排列的时候，出现了单谷就是几个双端队列。
当有相同元素的时候 需要特殊考虑。

blablabla

时间复杂度分析：blablabla

C++ 代码

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
typedef long long ll;

typedef struct Node
{
    ll val,x;
} Node;

int cmp(Node a,Node b)
{
    if(a.val == b.val)
        return a.x < b.x;
    return a.val < b.val;
}
Node node[200100];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld",&node[i].val);
        node[i].x = i;
    }
    sort(node + 1,node + 1 + n,cmp);
    int ans = 1;
    int point = 1;
    ll pre = 10010101000;
    for(int i = 1; i <= n; )
    {
        int j;
        j = i + 1;
        while(node[j].val == node[i].val)
            j ++;
        int mi = node[i].x,ma = node[j - 1].x;
        if(point)
        {
            if(pre > ma)
            {
                pre = mi;
            }
            else
            {
                pre = ma;
                point = 0;
            }
        }
        else
        {
            if(pre < mi)
            {
                pre = ma;
            }
            else
            {
                pre = mi;
                point = 1;
                ans ++;
            }
        }
        i = j;
    }
    printf("%d\n",ans);
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla