[BZOJ1660]&&[Usaco2006 Nov]Bad Hair Day 乱发节

2014-07-12
竞赛题解 / 基本数据结构
BZOJSTLUSACO

描述 Description

农民约翰的某 N(1 ≤ N ≤ 80000) 头奶牛正在过乱头发节！ 由于每头牛都意识到自己凌乱不堪的发型， 约翰希望统计出能够看到其他牛的头发的牛的数量．

每一头牛 t 有一个高度 hi( 1 ≤ hi ≤ 109 ). 所有 N 头牛面向东方排成一排，牛 N 在最前面，而牛 1 在最后面． 第 i 头牛可以看到她前面的那些牛的头， 只要那些牛的高度严格小于她的高度， 而且中间没有比 hi 高或相等的奶牛阻隔．

让 ci 表示第 i 头牛可以看到发型的牛的数量；请输出 \[sum_{i=1}^{N}c_{i}\]

输入格式 InputFormat

Line 1: 牛的数量 N。

Lines 2..N+1: 第 i+1 是一个整数，表示第 i 头牛的高度。

输出格式 OutputFormat

Line 1: 一个整数表示 c[1] 至 c[N] 的和。

样例输入 SampleInput

10
999999999
2
999999999
2
999999999
2
999999999
2
999999999
2

样例输出 SampleOutput

5

来源 Source

Silver

BZOJ 1660

代码 Code

维护一个单调栈。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
const int inf=0x7fffffff;
int a[80005];
int i,j,t,n,m,l,r,k,z,y,x;
long long ans;
stack <int> s;
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    a[n+1]=inf;
    ans=0;
    for (i=1;i<=n+1;i++)
    {
        while (!s.empty() && a[s.top()]<=a[i])
        {
            ans+=i-s.top()-1;
            s.pop();
        }
        s.push(i);
    }
    printf("%lld\n",ans);
    return 0;
}