MENU

Bindian Signalizing

2022 年 05 月 07 日 • 阅读: 13606 • 算法

这是 2010 年 Codeforces Beta Round #5 中的 E 题,曾在 2017 年 京东笔试 中出现,转载本题解请注明出处

题目大意

由 $n$ 座山峰构成的环形山脉,第 $i$ 座山峰的高度为 $h_i$,每座山峰设有一个瞭望台,请你计算能互相瞭望的山峰对数。两座山峰能互相瞭望的含义是,中间没有更高山峰

思路分析

对于任意一座山峰,与它能互相瞭望的最右端点一定是右侧最近且更高的山。我们想到单调栈可在 $O(n)$ 时间求出 $n$ 个数中每个数右侧最近且更大的数

维护一个严格单调递减栈,仅当遇到更大元素时,栈顶才需出栈,此时新元素是出栈元素右侧最近且更大的数。我们发现,栈顶出栈时,它已遇到能与其互相瞭望的最右端点。换句话说,从入栈到出栈间遇到的所有数便是右侧能与其互相瞭望的所有山峰。由于每个元素只出入栈一次,只要统计在此期间它们遇到的所有右端点,即可不重不漏算出答案

但进一步思考,由于山是环形,一直向右能回到自己左侧,而左侧已经把自己当成过右端点,这将导致重复解,必须找出这种情况发生的条件,并特殊处理。根据题意,只有中间无更高山峰时,两端才能互相瞭望,如果一直向右能跨越最高峰,就代表两端和最高峰等高。找到情况发生的条件后,考虑如何避免重复解,我们约定,和最高峰等高的山,只作为前面最高峰的右端点

实现细节

根据以上分析,我们首先需要知道最高峰高度,也需要判断前面是否遍历过最高峰。那么,不妨把某座最高峰当作起点,从它右侧下一座开始顺时针遍历,直到再次遇到该座最高峰时停止。由于是单调递减栈,这也意味着遍历过程不用判断栈空

由于可能存在高度相同山峰,把键值对 $(value,count)$ 作为栈内元素类型,表示有 $count$ 座高度为 $value$ 的山峰。当有新元素入栈时

  1. 栈顶小于新元素,需要出栈顶。由于新元素是栈顶右侧最近且更大的数,即新元素是栈顶能与其互相瞭望的最右端点,更右侧的山都不能与其互相瞭望,所以出栈后栈顶右侧山峰已统计完。由于栈顶可能包含多座高度相同山峰,新元素是它们共同的最右端点,所以答案加上栈顶 $count$
  2. 直到栈顶不小于新元素

    1. 栈顶等于新元素,新元素入栈,即令栈顶 $count$ 加一。在此之前,由于新元素与栈顶等高,能够作为栈顶右端点,所以答案加上栈顶 $count$。其次,如果栈顶下侧还存在一个元素,答案加一,因为下侧更高,新元素能作为它的右端点,又因为它阻挡了更左山峰,所以更下侧元素无需考虑
    2. 栈顶大于新元素,直接入栈。在此之前,由于它能作为栈顶右端点,所以答案加一。由于 $2.a$ 中的相同原因,栈顶以下元素无需考虑

所有元素都入栈一次后,如果栈不空,继续出栈。由单调栈性质,之所以栈内还剩余元素,是因为它们右侧都不存在比它们大的数,由此推出,最高峰是能与它们互相瞭望的最右端点

  1. 剩余三个以上元素。栈顶向右看能与最高峰互相瞭望,答案要加 $top.count$,出栈后它的右侧端点已统计完
    剩余三个以上元素
  2. 直到剩余两个元素

    1. 最高峰只有一座。虽然栈顶向右能找到最高峰与其互相瞭望,但 $TOP$ 中所有元素在入栈时,最高峰已把它们当成过右端点,见入栈分析 $2.a,\ 2.b$,此时不能重复统计
      剩余两个元素且最高峰只有一座
    2. 最高峰不止一座。栈顶向右能找到栈底第一座最高峰,因此答案要加上 $top.count$,出栈后其右侧端点已统计完
      剩余两个元素且不止一座最高峰
  3. 直到剩余一个元素,它一定是最高峰,无论有多少座,根据约定,后入栈的都已作为先入栈的右端点,见思路分析末段,因此不再重复统计

总结:计数类问题一定要保证统计方式不重不漏,尤其关注边界情况。如果没有明显的划分标准,考虑先加再减或先减再加

#include <iostream>

#define V first
#define C second

using namespace std;
using LL = long long;

const int N = 1e6 + 5;
int tt = -1, a[N];
pair<int, int> s[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n, mx_i = 0; cin >> n;
    
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        if (a[i] > a[mx_i]) mx_i = i;
    }
    
    LL ans = 0;
    s[++ tt] = {a[mx_i], 1};
    for (int i = mx_i + 1; i != mx_i; i = (i + 1) % n) {
        while (a[i] > s[tt].V) ans += s[tt --].C;
        if (a[i] == s[tt].V) ans += s[tt].C ++ + !!tt;
        else ans ++, s[++ tt] = {a[i], 1};
    }
    
    while (tt --) if (tt || s[0].C > 1) ans += s[tt + 1].C;

    cout << ans << '\n';

    return 0;
}
TG 大佬群 QQ 大佬群

最后编辑于: 2022 年 08 月 08 日
返回文章列表 文章二维码
本页链接的二维码
打赏二维码
添加新评论

Loading captcha...

已有 2 条评论
  1.  偶来了  偶来了   Mac OS X 10.15.7  Safari 16.4

    阅读后蒙蒙

  2. paul paul   Windows 10 x64 Edition  Google Chrome 110.0.0.0

    这位博主,您好。在浏览完您的博客文章后,感觉您的博客内容质量非常的好
    现诚挚地向您发出邀请,邀请您加入腾讯自媒体分享计划:https://cloud.tencent.com/developer/support-plan?invite_code=347bs58ysckks 。待审核成功入驻后,会在社区后台为您发放相关得腾讯云无门槛代金券以及一些实物奖励。
    具体审核细则,请进入页面查看。