链接:https://vjudge.net/problem/POJ-3250#author=Tiw_Air_OAO
题意:
给n个高度不同的奶牛,每个奶牛只能往右边看且比他矮的。
求每个奶牛能看到奶牛的和。
思路:
单调栈,每次加一个新牛,将比他矮的出栈,剩下的都是比他高的,表示他能被剩下的看到。
代码:
#include <iostream> #include <memory.h> #include <vector> #include <map> #include <algorithm> #include <cstdio> #include <math.h> #include <queue> #include <string> #include <stack> using namespace std; typedef long long LL; int main() { int n, a; LL res = 0; stack<int> r; scanf("%d", &n); for (int i = 1;i <= n;i++) { cin >> a; while (!r.empty() && a >= r.top()) r.pop(); res += r.size(); r.push(a); } printf("%lld ", res); return 0; }