当前位置: 代码迷 >> 综合 >> 【poj3250 牛的视野 Bad Hair Day】【单调栈】【寻找它和它右边第一个比它大的数之间有多少个数】
  详细解决方案

【poj3250 牛的视野 Bad Hair Day】【单调栈】【寻找它和它右边第一个比它大的数之间有多少个数】

热度:92   发布时间:2024-01-04 11:51:06.0

【链接】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);}
}