Codeforces Round #622 (Div. 2) C2. Skyscrapers (hard version)
问题
我是参考了这篇题解传送门,然后按着思路做出了的(但大佬题解中的sumr[]数组操作我没看懂，然后自己改了改)。
摘抄:
维护峰值最优
找左右边的第一个比自己小的元素，维护前缀和，找最大的峰值
l[i]:用单调栈维护左边第一个比它小的数
r[i]:用单调栈维护右边第一个比它小的数
suml[i]:左边的前缀和
sumr[i]:右边的前缀和
然后遍历一遍数组，找到最大的峰值在哪
代码
#include <cstdio>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <stack>
using namespace std;
#define ll long long
#define P pair<int,int>
const int N=5e5+10;
const ll INF = ~(1LL<<63);
ll a[N],b[N],l[N],r[N],suml[N],sumr[N];
int n;
stack<ll>st;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=n;i++)
{
while(st.size()&&a[st.top()]>=a[i])
st.pop();
if(st.empty())
l[i] = 0;
else
l[i] = st.top();
st.push(i);
}
while(st.size())
st.pop();
for(int i=n;i>=1;i--)
{
while(st.size()&&a[st.top()]>=a[i])
st.pop();
if(st.empty())
r[i] = n+1;
else
r[i] = st.top();
st.push(i);
}
for(int i=1;i<=n;i++)
suml[i] = suml[l[i]] + (i-l[i])*a[i];
for(int i=n;i>=1;i--)
sumr[i] = sumr[r[i]] + (r[i]-i)*a[i];
ll maxn = 0,pos;
for(int i=1;i<=n;i++)
{
ll cnt = suml[i] + sumr[i] - a[i];
if(maxn < cnt)
{
maxn = cnt;
pos = i;
}
}
b[pos] = a[pos];
for(int i=pos-1;i>=1;i--)
{
b[i] = min(b[i+1],a[i]);
}
for(int i=pos+1;i<=n;i++)
{
b[i] = min(a[i],b[i-1]);
}
for(int i=1;i<=n;i++)
{
cout << b[i] << " ";
}
return 0;
}