技术教程 编程代码 POJ 3250 Bad Hair Day --单调栈(单调队列?) 正文

POJ 3250 Bad Hair Day --单调栈(单调队列?)

2023-07-29,,

维护一个单调栈，保持从大到小的顺序，每次加入一个元素都将其推到尽可能栈底，知道碰到一个比他大的，然后res+=tail，说明这个cow的头可以被前面tail个cow看到。如果中间出现一个超级高的，自然会推到栈底，即此元素以前的cow看不到此元素后面cow的头，即res不会加此元素前面的个数，说明是正确的。

注意要用long long 或者 __int64类型。 刚开始看着80000不大的样子，其实最大情况下res有 1+2+....+80000 = 3200040000，超过int范围。以后还是验证一下，或者看到这种比较大的数还是优先用long long 或者 __int64类型吧。

代码：

#include <iostream>

#include <cstdio>

using namespace std;

#define N 80007

int a[N];

int main()

{

    int head,tail,n,x;

    ll res;

    while(scanf("%d",&n)!=EOF)

    {

        head = tail = ;

        res = ;

        while(n--)

        {

            scanf("%d",&x);

            while(tail > head && x >= a[tail-])

                tail--;

            a[tail++] = x;

            res += tail-;

        }

        printf("%lld\n",res);

    }

    return ;

}

POJ 3250 Bad Hair Day --单调栈(单调队列?)的相关教程结束。

《POJ 3250 Bad Hair Day --单调栈(单调队列?).doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!