Codeforces 1313C2 - Skyscrapers【思维】

题意：

要求在一条直线上建 $n$n 栋楼，并且要满足下列要求：
1.每栋楼的层数不能超过其楼层限制 $m\left[i\right]$m[i]；
2.对于第 $i,j,k$i,j,k 栋，如果满足： i<j<k，那么其层数要满足： aj​>ai​<ak​，其中 $j,k$j,k 不一定和 $i$i 相邻。
求出各个楼房的实际建筑层数。

思路：

  按题目要求，最终的所有的楼房的高度可以是：递增，递减，先增后减，或者在其中加一段不变的片段，但不能出现先减后增。那么最终就必然存在一个峰值，其他的楼房高度都不大于他的高度。所以，问题转化为如何找到该峰值的位置。不能以每栋楼房的限制高度为标准，找最大的，这样不能保证总的层数最小。而应该以总的楼层数为标准（废话 ），接下来讨论如何求出以各个点为峰值时对应的总楼层数。
  数组 $l\left[i\right]$l[i] 表示：以楼房 $i$i 为峰值时，其左边（包括自己）所有楼房的总层数。
  数组 $r\left[i\right]$r[i] 表示：以楼房 $i$i 为峰值时，其右边（包括自己）所有楼房的总层数。
  先讨论 $l\left[i\right]$l[i] 数组的求法，对于楼房 $i$i 而言，如果m[i]是1~i中的最小值，那么 $l\left[i\right]=i\ast m\left[i\right]$l[i]=i∗m[i]；否则，若 $j$j 为 $i$i 前面满足： {m[j]<m[i]且(i−j)最小}的楼房，那么 $l\left[i\right]=l\left[j\right]+m\left[i\right]\ast (i-j)$l[i]=l[j]+m[i]∗(i−j)。 $r\left[i\right]$r[i] 的求法同理。
关键在于如何维护每个 $i$i 前面小于 $m\left[i\right]$m[i] 且最靠近 $i$i的位置，具体见代码。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll m[N],l[N],r[N];
stack<int>sta;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&m[i]);
    for(int i=1;i<=n;i++)
    {
        while(!sta.empty()&&m[sta.top()]>m[i])
            sta.pop();
        if(sta.empty())
            l[i]=1LL*i*m[i];
        else
            l[i]=l[sta.top()]+1LL*(i-sta.top())*m[i];
        sta.push(i);
    }
    while(!sta.empty())
        sta.pop();
    for(int i=n;i>=1;i--)
    {
        while(!sta.empty()&&m[sta.top()]>m[i])
            sta.pop();
        if(sta.empty())
            r[i]=1LL*(n-i+1)*m[i];
        else
            r[i]=r[sta.top()]+1LL*(sta.top()-i)*m[i];
        sta.push(i);
    }
    ll ans=0;
    int p;
    for(int i=1;i<=n;i++)
    {
        if(l[i]+r[i]-m[i]>ans)
        {
            ans=l[i]+r[i]-m[i];
            p=i;
        }
    }
    for(int i=p-1;i>=1;i--)
    {
        if(m[i]>m[i+1])
            m[i]=m[i+1];
    }
    for(int i=p+1;i<=n;i++)
    {
        if(m[i]>m[i-1])
            m[i]=m[i-1];
    }
    for(int i=1;i<=n;i++)
        printf("%lld%c",m[i],i==n?'\n':' ');
    return 0;
}