Bindian Signalizing

2022-05-07T18:50:00

这是 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>

using namespace std;
using LL = long long;
#define V first
#define C second

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';
}
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »