網(wǎng)站運(yùn)營方案 網(wǎng)站建設(shè),蘇州網(wǎng)站推廣如何,專項培訓(xùn)網(wǎng)站建設(shè)方案,網(wǎng)站怎樣繞過360認(rèn)證問題描述 給定一個山脈的二維剖面#xff0c;由 NNN 個點(diǎn)組成#xff0c;每個點(diǎn)有一個海拔高度 HiH_iHi? #xff08;單位#xff1a;厘米#xff09;。 我們需要找出所有 Ultras exttt{Ultras}Ultras 山峰#xff0c;即那些地形突出度#xff08;topographic promine…問題描述給定一個山脈的二維剖面由NNN個點(diǎn)組成每個點(diǎn)有一個海拔高度HiH_iHi?單位厘米。 我們需要找出所有Ultras exttt{Ultras}Ultras山峰即那些地形突出度topographic prominence exttt{topographic prominence}topographic prominence大于等于150000150000150000厘米的山峰。地形突出度的定義對于海拔為hhh的山峰ppp其突出度定義為最大的ddd使得從ppp到任意更高山峰的任何路徑都必須經(jīng)過一個海拔為h?dh-dh?d的點(diǎn)。 如果沒有更高的山峰則突出度就是hhh本身。輸入格式第一行整數(shù)NNN3≤N≤1053 leq N leq 10^53≤N≤105表示點(diǎn)數(shù)。第二行NNN個整數(shù)HiH_iHi?0≤Hi≤1060 leq H_i leq 10^60≤Hi?≤106表示按順序排列的各點(diǎn)海拔。相鄰點(diǎn)海拔不同Hi≠Hi1H_i eq H_{i1}Hi?Hi1?。第一個和最后一個點(diǎn)在海平面H1HN0H_1 H_N 0H1?HN?0。保證至少有一個Ultra exttt{Ultra}Ultra。輸出格式輸出所有Ultras exttt{Ultras}Ultras的索引按出現(xiàn)順序 從111開始編號。題目分析這個問題本質(zhì)上是計算每個山峰的地形突出度然后篩選出滿足條件的山峰。 關(guān)鍵在于如何高效地計算突出度。突出度計算的核心對于位置iii的山峰海拔H[i]H[i]H[i]向左尋找找到左邊第一個嚴(yán)格更高的山峰位置LLL。 在區(qū)間(L,i)(L, i)(L,i)中找到最低海拔點(diǎn)記為leftMinleftMinleftMin。 如果左邊沒有更高山峰則leftMin0leftMin 0leftMin0可以下降到海平面。向右尋找找到右邊第一個嚴(yán)格更高的山峰位置RRR。 在區(qū)間(i,R)(i, R)(i,R)中找到最低海拔點(diǎn)記為rightMinrightMinrightMin。 如果右邊沒有更高山峰則rightMin0rightMin 0rightMin0。計算突出度如果左右都沒有更高山峰即LLL和RRR都不存在則突出度prominenceH[i]prominence H[i]prominenceH[i]。否則突出度prominenceH[i]?max?(leftMin,rightMin)prominence H[i] - max(leftMin, rightMin)prominenceH[i]?max(leftMin,rightMin)。判斷 $ exttt{Ultra}如果prominence≥150000prominence geq 150000prominence≥150000則iii是Ultra exttt{Ultra}Ultra。算法設(shè)計要點(diǎn)尋找左右第一個更高山峰可以使用單調(diào)棧。 從左到右掃描維護(hù)一個單調(diào)遞減棧嚴(yán)格來說是非遞增但要注意是“嚴(yán)格更高”所以彈出條件是H[棧頂]≤H[i]H[棧頂] leq H[i]H[棧頂]≤H[i]。同理從右到左掃描得到右邊第一個更高山峰。查詢區(qū)間最小值需要快速查詢?nèi)我鈪^(qū)間[l,r)[l, r)[l,r)的最小海拔值。由于NNN最大為10510^5105不能使用O(n2)O(n^2)O(n2)的暴力方法?？梢允褂肦MQRange Minimum Query exttt{RMQRange Minimum Query}RMQRange Minimum Query預(yù)處理實(shí)現(xiàn)O(1)O(1)O(1)查詢。這里采用稀疏表Sparse Table exttt{Sparse Table}Sparse Table實(shí)現(xiàn)RMQ exttt{RMQ}RMQ預(yù)處理O(nlog?n)O(n log n)O(nlogn)查詢O(1)O(1)O(1)。邊界處理第一個和最后一個點(diǎn)是海平面高度000不計入山峰。注意“嚴(yán)格更高”意味著海拔必須大于當(dāng)前山峰相等不算。當(dāng)左右都沒有更高山峰時突出度等于自身高度。算法步驟讀入數(shù)據(jù)。使用單調(diào)棧計算每個位置左邊第一個更高山峰的位置leftHigher[i]leftHigher[i]leftHigher[i]和右邊第一個更高山峰的位置rightHigher[i]rightHigher[i]rightHigher[i]。構(gòu)建稀疏表用于快速查詢?nèi)我鈪^(qū)間的最小海拔值。遍歷每個位置iii從111到N?2N-2N?2排除首尾海平面點(diǎn)查詢leftMinleftMinleftMin如果leftHigher[i]≠?1leftHigher[i] eq -1leftHigher[i]?1查詢區(qū)間(leftHigher[i],i)(leftHigher[i], i)(leftHigher[i],i)的最小值否則leftMin0leftMin 0leftMin0。查詢rightMinrightMinrightMin如果rightHigher[i]≠NrightHigher[i] eq NrightHigher[i]N查詢區(qū)間(i,rightHigher[i])(i, rightHigher[i])(i,rightHigher[i])的最小值否則rightMin0rightMin 0rightMin0。計算突出度。如果突出度≥150000geq 150000≥150000記錄索引。輸出結(jié)果。復(fù)雜度分析單調(diào)棧掃描O(N)O(N)O(N)稀疏表構(gòu)建O(Nlog?N)O(N log N)O(NlogN)查詢與遍歷O(N)O(N)O(N)總復(fù)雜度O(Nlog?N)O(N log N)O(NlogN)可以處理N≤105N leq 10^5N≤105的數(shù)據(jù)規(guī)模。代碼實(shí)現(xiàn)// Go up the Ultras// UVa ID: 12674// Verdict: Accepted// Submission Date: 2025-12-24// UVa Run Time: 0.100s//// 版權(quán)所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cinn){vectorinth(n);for(inti0;in;i)cinh[i];// 左邊第一個嚴(yán)格更高的位置vectorintleftHigher(n,-1);stackintst;for(inti0;in;i){while(!st.empty()h[st.top()]h[i])st.pop();if(!st.empty())leftHigher[i]st.top();st.push(i);}// 右邊第一個嚴(yán)格更高的位置while(!st.empty())st.pop();vectorintrightHigher(n,n);for(intin-1;i0;i--){while(!st.empty()h[st.top()]h[i])st.pop();if(!st.empty())rightHigher[i]st.top();st.push(i);}// 構(gòu)建稀疏表RMQ用于快速查詢區(qū)間最小值intlogn1;while((1logn)n)logn;vectorvectorintminTable(logn,vectorint(n));for(inti0;in;i)minTable[0][i]h[i];for(intk1;klogn;k)for(inti0;i(1k)n;i)minTable[k][i]min(minTable[k-1][i],minTable[k-1][i(1(k-1))]);// 區(qū)間最小值查詢函數(shù)autorangeMin[](intl,intr){if(lr)returnINT_MAX;intk31-__builtin_clz(r-l);returnmin(minTable[k][l],minTable[k][r-(1k)]);};// 計算每個山峰的突出度并找出 Ultrasvectorintultras;for(inti1;in-1;i){intleftMin0;if(leftHigher[i]!-1)leftMinrangeMin(leftHigher[i]1,i);intrightMin0;if(rightHigher[i]!n)rightMinrangeMin(i1,rightHigher[i]);intprominence;if(leftHigher[i]-1rightHigher[i]n)prominenceh[i];elseprominenceh[i]-max(leftMin,rightMin);if(prominence150000)ultras.push_back(i1);}// 輸出結(jié)果if(!ultras.empty()){coutultras[0];for(size_t i1;iultras.size();i)cout ultras[i];}cout ;}return0;}總結(jié)本題的關(guān)鍵在于理解地形突出度的定義并將其轉(zhuǎn)化為可計算的算法。 通過單調(diào)?？焖僬业矫總€山峰左右第一個更高山峰再結(jié)合RMQ exttt{RMQ}RMQ快速查詢區(qū)間最小值即可高效計算出每個山峰的突出度。 算法復(fù)雜度O(Nlog?N)O(N log N)O(NlogN)完全滿足題目要求。需要注意的細(xì)節(jié)包括“嚴(yán)格更高”意味著海拔必須大于不能等于。當(dāng)沒有更高山峰時突出度等于自身高度。海平面點(diǎn)高度000不計入山峰。區(qū)間查詢時注意邊界處理。這個問題的解法綜合運(yùn)用了單調(diào)棧和稀疏表兩種數(shù)據(jù)結(jié)構(gòu)是一道很好的練習(xí)題目。