Algoogle

Algorithm for Programming Contest

PKU 3250 Bad Hair Day

Category: PKU Tag: data-structure, stack

Bad Hair Day

問題概要


牛が横一列に右を向いてならんでいる.
各牛は高さh[i]の台に乗っていて, 自分より右側の高さが自分より低い牛を見ることができる.
そのとき, 各牛が見ることができる牛の数の総和を求めよ.

解法


自分以上の高さが現れた時, その牛はもうそれ以上牛を見ることが出来ないことを考えると, stackを用いることで解ける.
左から順に処理していって, 各牛よりstackのtopが低い間stackの一番上を取り除く.
残ったstackの要素の牛がその牛を見ることができるので, stackに残っている要素数を答えに足していけば良い.

コード


(3250.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>

#define int long long
using namespace std;

int N, h, top, ans;
int st[80010];

signed main(){
    scanf("%lld", &N);
    while(N--){
        scanf("%lld", &h);
        while(top > 0 and st[top-1] <= h) top--;
        ans += top;
        st[top++] = h;
    }
    printf("%lld\n", ans);
    return 0;
}

Comments