USACO2006NOV SILVER Bad Hair Day 乱发节

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Sep 12 19:07:12 CST 2018

In Category: NoCategory

Description：

求一列数每个数左边连续的比他小的长度的和。

$1\le n \le 80000$

Solution：

单调栈。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 80010

int h[MAXN];

int s[MAXN],top = 0;

int main()

{

	scanf("%d",&n);

	for(int i = n;i >= 1;--i)scanf("%d",&h[i]);

	long long ans = 0;

	for(int i = 1;i <= n;++i)

	{

		while(top != 0 && h[i] > h[s[top]])--top;

		ans += i - s[top] - 1;

		s[++top] = i;

	}

	cout << ans << endl;

	return 0;

}

In tag: 数据结构-单调栈

wjh15101051