Codeforces Round #622 (Div. 2).C2 - Skyscrapers (hard version)

第二次写题解，请多多指教！

http://codeforces.com/contest/1313/problem/C2 题目链接

不同于简单版本的暴力法，这个数据范围扩充到了五十万。所以考虑用单调栈的做法；

1.首先顺序逆序扫一遍，记录下每个点左边的最大高度和以及右边的最大高度和存在l[i] r[i] 两个数组中；

2.第二步从前往后扫一边两个数组，得出每个点左右两边的最大高度和 l[i]+r[i]-a[i]; 以此找出最优的制高点，并标记其位置；

3.从制高点出发，向两边求高度。反向时，每个点的最终高度应满足 a[i]=min(a[i],a[i+1])；正向时，每个点的最终高度 a[i]=min(a[i],a[i-1])；

最后输出最终数组即可；

上代码

#include<bits/stdc++.h>

using namespace std;

long long a[],l[],r[];

int main()

{

    stack<int>st;

    int n;

    cin>>n;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

    }

    for(int i=;i<=n;i++)

    {

        while(!st.empty()&&a[st.top()]>=a[i]) st.pop();

        if(st.empty()) l[i]=i*a[i];

        else l[i]=l[st.top()]+a[i]*(i-st.top());

        st.push(i);

    }

    while (!st.empty()) st.pop();

    for(int i=n;i>=;i--)

    {

        while(!st.empty()&&a[st.top()]>=a[i]) st.pop();

        if(st.empty()) r[i]=(n-i+)*a[i];

        else r[i]=r[st.top()]+a[i]*(st.top()-i);

        st.push(i);

    }

    long long zuigao=,idex;

    for(int i=;i<=n;i++)

    {

        if(r[i]+l[i]-a[i]>zuigao)

        {

            zuigao=r[i]+l[i]-a[i];

            idex=i;

        }

    }

    for(int i=idex-;i>=;i--)

    {

        a[i]=min(a[i+],a[i]);

    }

    for(int i=idex+;i<=n;i++)

    {

        a[i]=min(a[i-],a[i]);

    }

    for(int i=;i<=n;i++) cout<<a[i]<<" ";

 }

最后，简单说一下简单版本的做法，即省去前面的左右扫描的步骤。直接假设每个点为最高点枚举即可。较为简单不再赘述。

巴特西

Codeforces Round #622 (Div. 2).C2 - Skyscrapers (hard version)

最新文章

热门文章