[洛谷 2866,poj 3250]Bad Hair Day

题目链接

https://www.luogu.org/problem/P2866

http://poj.org/problem?id=3250

题解

我们可以维护一个单调递减栈来解决问题（何谓单调栈？就是满足栈内元素单调递增或递减的栈）。每次插入一个元素时，如果栈顶元素小于要插入的元素，就将栈顶弹出，直到栈顶元素严格大于要插入的元素为止，此时栈内元素的个数即为 \(c_i\) 的值。

将操作重复 \(n\) 次，即可算出结果。

#include <iostream>
#include <algorithm>
using namespace std;
int a[80005],st[80005],t;
long long sum;
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i];
  while(t&&st[t]<=a[i])//将所有会挡住的牛都出栈
   t--;
  sum+=t;//累加结果
  st[++t]=a[i];//入栈操作
 }
 cout<<sum;
 return 0;
}