CF1313 C2

Skyscrapers

原题链接

大致题意:

有若干个高楼,每个高楼都有ai的高度限制,同时要满足没有一幢高楼比它相邻的两幢高楼都低,即没有i既满足 j<i<k又满足 aj> ai<ak

Examples

input

5
1 2 3 2 1

output

1 2 3 2 1 

input

3
10 6 8

output

10 6 6 

其实这题的结果最后一定是一个单峰的图像(左边单调递增,右边单调递减)为什么呢?

因为如果有两个峰,那么必然会产生一个谷底,那么就不满足题意。

也就是说我们只要找到那个单峰,然后贪心的模拟就好了。

最简单的方法来寻找结果最大的单峰就是直接枚举,也是这题easy版本的做法,n为1000。

但是这题的n有5e6,显然不能枚举了。

由于其左右两边分别具有单调性,我们不如去维护这两个数组

s1[i] 表示从1-i满足单调递增的前提下最大的sum

s2 [i] 表示从i-n满足单调递减的前提下最大的sum

如果 a[i]>=a[i-1] 那么s1[i]=s1[i-1]+a[i];

a[i]<a[i-1] 那么我们需要从a[i-1]开始倒着往前找到第一个<=a[i]的数,然后把原本>a[i]的数都变成a[i]来维护

刚开始我是按照这个思路来维护,发现还是会tle,然后参考了一下题解,把单调栈里存的a[i]改成i下标就好了,这样就不用一个一个去push和pop了。

注意:使用stack.top( )之前一定要判断下是否为空!!!

AC代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
#define ll long long
#define inf 0x3f3f3f3f
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int maxn=5e5+10;
ll a[maxn],s1[maxn],s2[maxn];
stack<int>s;
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

	for(int i=1;i<=n;i++)
	{	s1[i]=s1[i-1];
		if(a[i]>=a[i-1]) s.push(i),s1[i]+=a[i];
		else
		{
			while(!s.empty()&&a[s.top()]>a[i]) 
				s.pop();
			if(!s.empty())
			s1[i]=s1[s.top()]+(i-s.top())*a[i];
			else s1[i]=a[i]*i;
			s.push(i);	
		}
	}
	while(!s.empty()) s.pop();
	for(int i=n;i>=1;i--)
	{	s2[i]=s2[i+1];
		if(a[i]>=a[i+1]) s.push(i),s2[i]+=a[i];
		else
		{
			while(!s.empty()&&a[s.top()]>a[i]) s.pop();
			if(!s.empty())
			s2[i]=s2[s.top()]+(s.top()-i)*a[i];
			else s2[i]=a[i]*(n-i+1);
			s.push(i);	
		}
	}
	ll maxx=0,maxi;
	for(int i=1;i<=n;i++)
	{
		if(s1[i]+s2[i]-a[i]>maxx)
		{
			maxi=i;
			maxx=s1[i]+s2[i]-a[i];
		}
	}
//	for(int i=1;i<=n;i++)
//	debug(s1[i]),debug(s2[i]);
//	debug(maxi); 
	for(int i=maxi-1;i>=1;i--)
	a[i]=min(a[i],a[i+1]);
	for(int i=maxi+1;i<=n;i++)
	a[i]=min(a[i],a[i-1]);
	cout<<a[1];
	for(int i=2;i<=n;i++)
	cout<<" "<<a[i];
}