X - Skyscrapers (hard version) CodeForces

题目大意：n个高楼，每个楼最高为mi,要求，第i个楼左边和右边不能有同时比它高的楼。让你求最在n个楼总和最高的情况下，每个楼的高度。

题解：用单调栈来做，n个楼的高度要么是单调递减，要么是单调递增，要么就是先曾后减，就这3种情况，其他的不可能。

维护一个单调非递减的栈，并且维护一个数组ans[]，第i个位置，维护的是i左边的所有楼的最大高度和。

当新元素比栈顶元素大时或者直接ans[i]=m[i]+ans[i-1]。当新元素比栈顶元素小时，一直出栈，直到栈为空(ans[i]=arr[i]*i)，或者找到一个比新元素小于等于设为top的，也就是说top到i之间的元素都要比i元素大

所以ans[i]=ans[i-1]+arr[i]*(i-top)。然后数组逆序在来一遍。

遍历一遍数组，拼接左端与右端，找到和最大时的峰值。然后......

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=5E5+;

ll arr[N];

ll lans[N];

ll rans[N];

ll n;

void solve(ll ans []){

    stack<ll >st;

    ans[]=;

    for(ll i=;i<=n;i++){

        if(st.empty()) {

            st.push(i);

            ans[i]=arr[i]+ans[i-];

        }

        else {

            ll top=st.top();

            while(st.size()&&arr[i]<arr[top]){

                st.pop();

                if(st.empty()) {

                    break;

                }

                top=st.top();

            }

            if(st.empty()) ans[i]=i*arr[i];

            else {

                top=st.top();

                ans[i]=arr[i]*(i-top)+ans[top];

            }

            st.push(i);

        }

    }

}

int main()

{

    cin>>n;

    for(ll i=;i<=n;i++) cin>>arr[i];

    solve(lans);

    reverse(arr+,arr++n);

    solve(rans);

    ll ans=,pos;

    for(ll i=;i<=n;i++){

        ll c=lans[i]+rans[n-i];

        if(c>=ans) {

            ans=c;

            pos=i;

        }

    }

    reverse(arr+,arr++n);

    for(ll i=pos-;i>=;i--){

        if(arr[i]>arr[i+]) arr[i]=arr[i+];

    }

    for(ll i=pos+;i<=n;i++) {

        if(arr[i]>arr[i-]) arr[i]=arr[i-];

    }

    for(ll i=;i<=n;i++) cout<<arr[i]<<" ";

    return ;

}

巴特西

X - Skyscrapers (hard version) CodeForces - 1313C2

最新文章

热门文章