本文主要是介绍【poj3250 牛的视野 Bad Hair Day】【单调栈】【寻找它和它右边第一个比它大的数之间有多少个数】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【链接】http://poj.org/problem?id=3250
【题意】
一群高度不完全相同的牛从左到右站成一排，每头牛只能看见它右边的比它矮的牛的发型，若遇到一头高度大于或等于它的牛，则无法继续看到这头牛后面的其他牛。给出这些牛的高度，要求每头牛可以看到的牛的数量的和。
【分析】
把要求作一下转换，其实就是要求每头牛被看到的次数之和。这个可以使用单调栈来解决。
【单调栈】https://blog.csdn.net/zuzhiang/article/details/78134247
【变式】
那就是给出N块竖直的木板的高度，现在在第 i 块木板的右方加水，问可以水可以淹没多少木板。
【代码】
#pragma warning(disable:4996)
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<double, int>pdi;
typedef long long ll;
#define CLR(a,b) memset(a,b,sizeof(a))
#define _for(i, a, b) for (int i = a; i < b; ++i)
const int mod = (int)1e9 + 7;
const long double eps = 1e-10;
const int maxn = 8e5 + 7;
const int INF = 0x3f3f3f3f;int a[maxn];
int st[maxn];int main() {int n;while (~scanf("%d", &n)) {int x;int top = 0;ll ans = 0;for (int i = 0; i < n; i++) {scanf("%d", &x);while (top&&st[top - 1] <= x)--top;ans += top;st[top++] = x;}printf("%lld\n", ans);}
}
这篇关于【poj3250 牛的视野 Bad Hair Day】【单调栈】【寻找它和它右边第一个比它大的数之间有多少个数】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
