首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

Codeforces 305B Mike and Feet:單調棧求各長度區間最小值的最大值

     編輯:關於C++

題目大意

n (≤2×10⁵) 隻熊站成一排,高度 a[i]。對每個長度 x (1≤x≤n),求所有長度為 x 的連續區間中,最小值的最大值。

單調棧 + 長度貢獻

對每個元素 a[i],找到它作為最小值的最大區間:左邊界 L[i] 為左側第一個 < a[i] 的位置,右邊界 R[i] 為右側第一個 < a[i] 的位置。則 a[i] 是長度 len = R[i] - L[i] - 1 區間內的最小值,且對於所有 ≤ len 的長度,a[i] 都可能是最小值的候選。
用單調遞增棧求 L[i], R[i]。維護 ans[len] = max(ans[len], a[i])。
最後從 n-1 遞減到 1:ans[i] = max(ans[i], ans[i+1])(長度更長的區間最小值的最大值,對較短長度也成立)。

C++ 實現

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved