首页 > 其他 > 详细

[单调栈] poj 3250 Bad Hair Day

时间:2015-08-10 16:12:38      阅读:263      评论:0      收藏:0      [点我收藏+]

题意:

一排母牛站成一排,给出牛的身高,每只牛都只能往右看,对于每只母牛有一个c[i]

c[i]代表i能看见多少只牛,矮的牛看不见高的牛,问所有c[i]的和是多少。

思路:

我们转换一下,其实就是求对于每只母牛能被看见多少次,显然是对于它往左单调递增的牛都能看见它

那么我们维护一个这样的单调栈,每次都将小于等于它的出栈,那么栈中的元素的个数就是能看见它的个数

这样再把该元素插入栈就好了。

代码:

#include"cstdlib"
#include"cstring"
#include"cmath"
#include"cstdio"
#include"queue"
#include"algorithm"
#include"iostream"
#include"stack"
using namespace std;
#define ll __int64
int main()
{
    int n;
    while(scanf("%d",&n)!=-1)
    {
        stack<int>q;
        ll ans=0;
        while(n--)
        {
            int x;
            scanf("%d",&x);
            while(!q.empty() && q.top()<=x) q.pop();
            ans+=q.size();
            q.push(x);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

[单调栈] poj 3250 Bad Hair Day

原文:http://blog.csdn.net/wdcjdtc/article/details/47399205

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!