题目链接（牛客网）：[USACO 2006 Nov S]Bad Hair Day (nowcoder.com)
视频教程：[USACO 2006 Nov S]Bad Hair Day（单调栈）_哔哩哔哩_bilibili
题目大意：
FJ有n只牛（0 <= n <= 80,000），每只牛有一个独特的身高（不会出现一样高的牛），每头牛向右看，能看见所有比自己矮的牛，直到遇到比自己高的牛，那么后面的牛都看不见了。求所有牛能看见的牛的数量和。
思路
观察一下题干，这里用了一个带方向的序列（都向右看）来表示牛的状态，并且需要维护一段区间内的数量，并且有明显的大小关系。容易想到用单调栈来解决，因为牛的右边是有效区间，左边就看不到了，所以我们考虑从右往左构造单调递减栈。
为什么是单调递减栈呢？因为当一只牛往右看遇到比自己大的就要停，相当于从右往左的一个较高的牛（设为X）右边的牛都不会被看到，可以被收缩到X中，如果出现了比X更高的牛，那么X右边所有牛都会被看到，否则都不被看到，容易想到X右边的应该全部小于X，那么如果X右边出现了比X高的，就应该增加一个节点。
所以是从右往左的单调递减栈，每个节点存两个信息，高度和这头牛能看见的牛的数量。
代码
/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long
//请使用%lld输出long long类型数据
using namespace std;
inline int re(){
int s = 0,w = 1;char c = gc();
while(c > '9' || c < '0'){if(c == '-')w = -1;c = gc();}
while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
return s * w;
}
//单调栈，构造单调递减栈
/*-------全局变量------*/
typedef pair<int, int> PII;
const int maxn = 8e4 + 10;
int N, h[maxn], top = 0;
PII stk[maxn];//{高度，数量}，这个数量表示该牛可以看见的牛的数量（不包括自身）
/*-----自定义函数------*/
signed main()
{
//freopen("in.txt","r",stdin);
N = re();
for(int i = 1;i <= N; ++ i)h[i] = re();
int ans = 0;
for(int i = N;i >= 1; -- i)
{
int cnt = 0;
while(top && stk[top].fi < h[i])cnt += stk[top --].se + 1;
ans += cnt;
stk[++ top] = {h[i], cnt};
/*debug
pr("now, stk = ");
for(int i = 1;i <= top; ++ i)pr("(%lld, %lld) ",stk[i].fi,stk[i].se);
pr("\n");
*/
}
pr("%lld\n",ans);
return 0;
}
文章评论