当前位置: 代码迷 >> 综合 >> POJ3250 Bad Hair Day(单调栈)
  详细解决方案

POJ3250 Bad Hair Day(单调栈)

热度:91   发布时间:2024-01-16 13:45:07.0

题意:

给出一列牛的高度,所有牛只能往右看,且只能看到高度比自己低的牛的发型,并且如果出现高度大于自己的牛,后面的牛就再也看不到了,求所有牛能看到其他牛的发型总和。

要点:

刚刚教了单调栈和单调队列,虽然原理了解了,但是还是无法很好的转化,这就需要练习了。这题主要是看到牛的总数与被看到的牛的数量是相等的,所以直接用单调递减栈,当前数与单调栈内的所有数比较,遍历弹出一遍后剩下的数就是能看到自己的牛数,最后加起来就行。


15401911 Seasonal 3250 Accepted 476K 188MS C++ 287B 2016-04-17 09:39:20
#include<stdio.h>
#define maxn 80005
int stack[maxn];int main()
{int top=0, num, n;long long ans = 0;scanf("%d", &n);while (n--){scanf("%d", &num);while (top > 0 && stack[top-1] <= num)//高度相同的也是看不到的top--;ans += top;stack[top++] = num;}printf("%lld", ans);return 0;
}