P2866 [USACO06NOV]糟糕的一天Bad Hair Day

题目链接：Miku

这道题看第一眼可能想到暴搜，从每个点开始向右找到第一个大于它的点并且计算距离

然而绝对会TLE

这时候我们就要找到一个数据结构了——单调栈。

单调栈，顾名思义，就是和单调队列一样的东西。只不过一个是栈，一个

是队列

（不知道单调队列是什么：这）

所谓单调，就是里面的元素都是按照某一关键字递增或递减。那么，我们怎样实现单调栈呢？
---------------------------------------------------

比如说我们要建立一个元素递增的栈，首先，我们在放入每一个元素时要进行判断，如果这个元素大于栈顶元素，我们就把它压进去

反之，如果我们直接压进去们就会破坏单调性，那么我们就需要不断地弹出栈顶元素，直到栈为空或符合第一条。

再来看一看代码（主要看注释）

 1 #include<iostream>
 2 #include<stack>
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 long long ans;
 6 stack <int> s;
 7 int n;
 8 int now;
 9 int main(){
10     cin>>n; 
11     for(int i=1;i<=n;++i)
12     {
13         cin>>now;
14         if(!s.size())//特判（好像不用？） 
15         {
16             s.push(now);
17             continue;
18         }
19         else{
20         while(s.size()&&s.top()<=now)//这是单调栈 
21         s.pop();
22         ans+=s.size();//计算答案 
23         //只要这个新元素小于栈顶，它就必然小于栈内的每个元素
24         //所以我们把栈的大小加给答案即可 
25         }
26         s.push(now);
27     }
28     cout<<ans;
29     return 0;
30 }

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论