首页 > 其他 > 详细

Skyscrapers

时间:2020-02-24 21:05:50      阅读:62      评论:0      收藏:0      [点我收藏+]

C2 - Skyscrapers (hard version)

分别用s1[i],s2[i]表示在 i 位置能取到的左边的值之和,右边的值之和。

利用单调栈的思想。

降低复杂度的方法是,充分利用重复计算的数据,将其保存下来,避免多次计算。

// Created by CAD on 2020/2/24.
#include <bits/stdc++.h>

#define fi first
#define se second
#define pli pair<long long,int>
#define ll long long
using namespace std;

const int maxn=5e5+5;
int m[maxn];
ll s1[maxn],s2[maxn];
stack<pli> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i)
        cin>>m[i];
    s.push({0,0});
    for(int i=1;i<=n;++i){
        while(s.top().fi>m[i]) s.pop();
        s1[i]=1ll*(i-s.top().se)*m[i]+s1[s.top().se];
        s.push({m[i], i});
    }
    while(s.size()) s.pop();
    s.push({0,0});
    for(int i=1;i<=n;++i){
        while(s.top().fi>m[n-i+1]) s.pop();
        s2[n-i+1]=1ll*(i-s.top().se)*m[n-i+1]+s2[n-s.top().se+1];
        s.push({m[n-i+1], i});
    }
    ll msum=0,bj=0;
    for(int i=1;i<=n;++i)
        if(msum<s1[i]+s2[i]-m[i]) msum=s1[i]+s2[i]-m[i],bj=i;
    int maxx=m[bj];
    for(int i=bj-1;i>=1;--i)
        m[i]=min(maxx,m[i]),maxx=m[i];
    maxx=m[bj];
    for(int i=bj+1;i<=n;++i)
        m[i]=min(maxx,m[i]),maxx=m[i];
    for(int i=1;i<=n;++i)
        cout<<m[i]<<" \n"[i==n];
    return 0;
}

Skyscrapers

原文:https://www.cnblogs.com/CADCADCAD/p/12358330.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!