ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[USACO 2006 Nov S]Bad Hair Day(单调栈)

2022年2月24日 769点热度 0人点赞 0条评论

题目链接(牛客网):[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;
}


本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: 单调栈 数据结构 牛客网
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意:
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号