[洛谷 2866,poj 3250]Bad Hair Day

题目链接

https://www.luogu.org/problemnew/show/P2866

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

题解

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

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

注意:结果需要用long long存储。

#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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注