双端队列

我就是我 2021-12-10 11:09 230阅读 0赞

题目连接：  
[https://www.acwing.com/problem/content/136/][https_www.acwing.com_problem_content_136]

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

#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);
    }

[https_www.acwing.com_problem_content_136]: https://www.acwing.com/problem/content/136/