放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

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

目录

挑战程序设计竞赛第二版.jpg

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;
}
16469445 hankcs 3250 Accepted 488K 157MS C++ 590B 2017-01-12 10:31:16

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

#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;
}
16469354 hankcs 3250 Accepted 1052K 454MS C++ 543B 2017-01-12 09:57:11

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

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机