C. Skyscrapers
原題傳送門
Problem Restatement
第一行有一個整數 \(n\ (1 \leq n \leq 500000)\)，表示發展商購買了 \(n\) 塊地，
第二行，\(n\) 個整數 \(m_1, m_2, \ldots, m_n\ (1 \leq m_i \leq 10^9)\)，表示每塊地上建摩天大廈層數的限制，
求讓每塊地上摩天大廈的樓層數之和最大，而且存在最高點\(a_i\)，讓它左邊的樓遞增，右邊的樓遞減，
Solution
\(O(n^2)\)的做法就不贅述了，
關鍵在于在遍歷最高點的時候，如何快速計算出其左右兩邊依次遞減之和，
首先可以想到遍歷用線段樹維護區間和，然后二分找到上一個比該節點大的點，后面全部區間染色成\(m[i]\)即可，復雜度\(O(nlog^2n)\)，代碼可參見Codeforces Submission，
然而實際上可以在構造線段樹的同時，維護一個區間最大值，然后利用線段樹自己的二分結構進行二分，同樣區間染色，復雜度\(o(nlogn)\)，這個代碼我沒寫QAQ，
不過思考能否不維護一個完整的序列，發現可以用單調堆疊來維護\(i\)前面的單調上升的堆疊，然后利用類似DP的思想，利用堆疊頂元素已經求好的前綴和外加區間染色后的和，均攤復雜度為\(O(n)\)，代碼如下，
Code
#include <bits/stdc++.h>
#define LL long long
#define MAXN 500005
using namespace std;
LL m[MAXN],ls[MAXN],rs[MAXN];
stack<int> st;
void solve(){
int n;
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%lld", &m[i]);
for(int i=1;i<=n;i++){
while(!st.empty() && m[st.top()]>m[i])
st.pop();
if(!st.empty()) ls[i]=ls[st.top()]+m[i]*(i-st.top());
else ls[i]=m[i]*i;
st.push(i);
}
st=stack<int>();
for(int i=n;i>=1;i--){
while(!st.empty() && m[i]<m[st.top()])
st.pop();
if(!st.empty()) rs[i]=rs[st.top()]+m[i]*(st.top()-i);
else rs[i]=m[i]*(n-i+1);
st.push(i);
}
LL mx=0,mi=0;
for(int i=n;i>=1;i--)
if(ls[i]+rs[i]-m[i]>mx)
mx=ls[i]+rs[i]-m[i], mi=i;
for(int i=mi-1;i>=1;i--)
m[i]=min(m[i],m[i+1]);
for(int i=mi+1;i<=n;i++)
m[i]=min(m[i],m[i-1]);
for(int i=1;i<=n;i++)
printf("%lld ", m[i]);
}
int main(){
int T=1;
// scanf("%d", &T);
while(T--){
solve();
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79556.html
標籤：其他
上一篇：交替方向乘子法（Alternating Direction Method of Multipliers）
下一篇：波束形成演算法綜述