POJ 3250 Bad Hair Day​ 题解《挑战程序设计竞赛》

POJ 3250 Bad Hair Day 

洗剪吹：N个人排队理发，每个人只能看到更矮的人的头，否则视线被挡住。给定他们的身高，求所有人能看到的人头之和。

4.4常用技巧精选（二） 

栈 

两种思路，第一种是All nearest smaller values的逆问题，即找到最近的greater or equal值，将两者下标做差。

#include<iostream>
#include <stack>

using namespace std;
#define MAX_N 80000

int N;
int h[MAX_N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", h + i);
    }
    stack<int> sta;
    long long ans = 0;
    for (int i = N - 1; i >= 0; --i)
    {
        for (; !sta.empty() && h[sta.top()] < h[i]; sta.pop());
        ans += (sta.empty() ? N : sta.top()) - i - 1;
        sta.push(i);
    }
    printf("%lld\n", ans);
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

另一种是转换思路，求每个人头能被几个人看到。明显只能被比自己高的人看到，用一个严格单调递增的栈维护比自己高的人的身高，将栈的大小累加即得到最终答案。

#include<iostream>
#include<stack>

using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int N, h;
    scanf("%d", &N);
    scanf("%d", &h);
    stack<int> sta;
    sta.push(h);
    long long ans;
    for (int i = 1; i < N; i++)
    {
        scanf("%d", &h);
        while (!sta.empty() && sta.top() <= h)
        {
            sta.pop();
        }
        ans += sta.size();
        sta.push(h);
    }
    printf("%lld\n", ans);

#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

两种思路都用到了栈，核心代码是类似的，视角不同而已。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3250 Bad Hair Day​ 题解《挑战程序设计竞赛》