当前位置：首页 > news >正文

UVa 12674 Go up the Ultras

news 2026/5/12 20:38:46

问题描述

给定一个山脉的二维剖面，由NNN个点组成，每个点有一个海拔高度HiH_iHi（单位：厘米）。我们需要找出所有Ultras\texttt{Ultras}Ultras山峰，即那些地形突出度（topographic prominence\texttt{topographic prominence}topographic prominence）大于等于150000150000150000厘米的山峰。

地形突出度的定义

对于海拔为hhh的山峰ppp，其突出度定义为最大的ddd，使得从ppp到任意更高山峰的任何路径都必须经过一个海拔为h−dh-dh−d的点。如果没有更高的山峰，则突出度就是hhh本身。

输入格式

第一行：整数NNN（3≤N≤1053 \leq N \leq 10^53≤N≤105），表示点数。
第二行：NNN个整数HiH_iHi（0≤Hi≤1060 \leq H_i \leq 10^60≤Hi≤106），表示按顺序排列的各点海拔。
相邻点海拔不同（Hi≠Hi+1H_i \neq H_{i+1}Hi=Hi+1）。
第一个和最后一个点在海平面（H1=HN=0H_1 = H_N = 0H1=HN=0）。
保证至少有一个Ultra\texttt{Ultra}Ultra。

输出格式

输出所有Ultras\texttt{Ultras}Ultras的索引（按出现顺序，从111开始编号）。

题目分析

这个问题本质上是计算每个山峰的地形突出度，然后筛选出满足条件的山峰。关键在于如何高效地计算突出度。

突出度计算的核心

对于位置iii的山峰（海拔H[i]H[i]H[i]）：

向左寻找：找到左边第一个严格更高的山峰位置LLL。在区间(L,i)(L, i)(L,i)中找到最低海拔点，记为leftMinleftMinleftMin。如果左边没有更高山峰，则leftMin=0leftMin = 0leftMin=0（可以下降到海平面）。
向右寻找：找到右边第一个严格更高的山峰位置RRR。在区间(i,R)(i, R)(i,R)中找到最低海拔点，记为rightMinrightMinrightMin。如果右边没有更高山峰，则rightMin=0rightMin = 0rightMin=0。
计算突出度：
- 如果左右都没有更高山峰（即LLL和RRR都不存在），则突出度prominence=H[i]prominence = H[i]prominence=H[i]。
- 否则，突出度prominence=H[i]−max⁡(leftMin,rightMin)prominence = H[i] - \max(leftMin, rightMin)prominence=H[i]−max(leftMin,rightMin)。
判断 $\texttt{Ultra}￥：如果prominence≥150000prominence \geq 150000prominence≥150000，则iii是Ultra\texttt{Ultra}Ultra。

算法设计要点

寻找左右第一个更高山峰：
- 可以使用单调栈。从左到右扫描，维护一个单调递减栈（严格来说是非递增，但要注意是“严格更高”，所以弹出条件是H[栈顶]≤H[i]H[栈顶] \leq H[i]H[栈顶]≤H[i]）。
- 同理，从右到左扫描得到右边第一个更高山峰。
查询区间最小值：
- 需要快速查询任意区间[l,r)[l, r)[l,r)的最小海拔值。
- 由于NNN最大为10510^5105，不能使用O(n2)O(n^2)O(n2)的暴力方法。
- 可以使用RMQ（Range Minimum Query）\texttt{RMQ（Range Minimum Query）}RMQ（Range Minimum Query）预处理，实现O(1)O(1)O(1)查询。
- 这里采用稀疏表（Sparse Table\texttt{Sparse Table}Sparse Table）实现RMQ\texttt{RMQ}RMQ，预处理O(nlog⁡n)O(n \log n)O(nlogn)，查询O(1)O(1)O(1)。
边界处理：
- 第一个和最后一个点是海平面（高度000），不计入山峰。
- 注意“严格更高”意味着海拔必须大于当前山峰，相等不算。
- 当左右都没有更高山峰时，突出度等于自身高度。

算法步骤

读入数据。
使用单调栈计算每个位置左边第一个更高山峰的位置leftHigher[i]leftHigher[i]leftHigher[i]和右边第一个更高山峰的位置rightHigher[i]rightHigher[i]rightHigher[i]。
构建稀疏表，用于快速查询任意区间的最小海拔值。
遍历每个位置iii（从111到N−2N-2N−2，排除首尾海平面点）：
- 查询leftMinleftMinleftMin：如果leftHigher[i]≠−1leftHigher[i] \neq -1leftHigher[i]=−1，查询区间(leftHigher[i],i)(leftHigher[i], i)(leftHigher[i],i)的最小值；否则leftMin=0leftMin = 0leftMin=0。
- 查询rightMinrightMinrightMin：如果rightHigher[i]≠NrightHigher[i] \neq NrightHigher[i]=N，查询区间(i,rightHigher[i])(i, rightHigher[i])(i,rightHigher[i])的最小值；否则rightMin=0rightMin = 0rightMin=0。
- 计算突出度。
- 如果突出度≥150000\geq 150000≥150000，记录索引。
输出结果。

复杂度分析

单调栈扫描：O(N)O(N)O(N)
稀疏表构建：O(Nlog⁡N)O(N \log N)O(NlogN)
查询与遍历：O(N)O(N)O(N)
总复杂度：O(Nlog⁡N)O(N \log N)O(NlogN)，可以处理N≤105N \leq 10^5N≤105的数据规模。

代码实现

// Go up the Ultras// UVa ID: 12674// Verdict: Accepted// Submission Date: 2025-12-24// UVa Run Time: 0.100s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cin>>n){vector<int>h(n);for(inti=0;i<n;i++)cin>>h[i];// 左边第一个严格更高的位置vector<int>leftHigher(n,-1);stack<int>st;for(inti=0;i<n;i++){while(!st.empty()&&h[st.top()]<=h[i])st.pop();if(!st.empty())leftHigher[i]=st.top();st.push(i);}// 右边第一个严格更高的位置while(!st.empty())st.pop();vector<int>rightHigher(n,n);for(inti=n-1;i>=0;i--){while(!st.empty()&&h[st.top()]<=h[i])st.pop();if(!st.empty())rightHigher[i]=st.top();st.push(i);}// 构建稀疏表（RMQ）用于快速查询区间最小值intlogn=1;while((1<<logn)<=n)logn++;vector<vector<int>>minTable(logn,vector<int>(n));for(inti=0;i<n;i++)minTable[0][i]=h[i];for(intk=1;k<logn;k++)for(inti=0;i+(1<<k)<=n;i++)minTable[k][i]=min(minTable[k-1][i],minTable[k-1][i+(1<<(k-1))]);// 区间最小值查询函数autorangeMin=[&](intl,intr){if(l>=r)returnINT_MAX;intk=31-__builtin_clz(r-l);returnmin(minTable[k][l],minTable[k][r-(1<<k)]);};// 计算每个山峰的突出度并找出 Ultrasvector<int>ultras;for(inti=1;i<n-1;i++){intleftMin=0;if(leftHigher[i]!=-1)leftMin=rangeMin(leftHigher[i]+1,i);intrightMin=0;if(rightHigher[i]!=n)rightMin=rangeMin(i+1,rightHigher[i]);intprominence;if(leftHigher[i]==-1&&rightHigher[i]==n)prominence=h[i];elseprominence=h[i]-max(leftMin,rightMin);if(prominence>=150000)ultras.push_back(i+1);}// 输出结果if(!ultras.empty()){cout<<ultras[0];for(size_t i=1;i<ultras.size();i++)cout<<" "<<ultras[i];}cout<<"\n";}return0;}