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

题目链接 :

C2. Skyscrapers (hard version)

题目描述 :

与上一道题类似,只是数据范围变大, 5e5, 如果用我们原来的方法,铁定是超时的。

考察点 :

单调栈,贪心,前缀和,后缀和

析题得侃:

上面说了,用原先得方法得话是铁定超时的,那怎么优化呢？通过 easy version ,我们可以

得知合适的位置一定是由两部分组成的,左侧的数的和,右侧的数的和,我们求这些和的时候

也确实浪费了大量的时间,我们能否知道这个位置,然后直接得到这个位置的和呢？然后直接

取一下最大值。

我们知道左右两侧一定是单调的,那么既然是单调的,我们能不能用单调栈来维护呢？

显然是可以的。

怎么维护呢？

看一组数据 :

下标 : 1 2 3 4 5 6

数值 : 5 2 3 6 7 4 （假设现在都在左侧,还没有找到合适的中间位置）

我们发现 2 的左侧必须 <= 2,同样的, 4 的左侧必须 <= 4,但是 有些数本来就比 4 小

所以 pre[6] = pre[3] + a[6] * (6 - 3)

同理,后缀也是一样的,逆过来就可以了

接下来我们要求某个位置的和就是 : sum = pre[i] + suf[i + 1]

Code：

#include <stack>

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 5e5 + 10;

typedef long long LL;

LL a[maxn],pre[maxn],suf[maxn];

LL L[maxn],R[maxn];

int n;

stack<int>S;

int main(void) {

	scanf("%d",&n);

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

		scanf("%lld",&a[i]);

	}

        // 便于我们处理,可以先入栈一个 0

	S.push(0);

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

		while(a[i] <= a[S.top()]) S.pop();

		L[i] = S.top();

		S.push(i);

	}

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

        //同上

	S.push(n + 1);

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

		while(a[i] <= a[S.top()]) S.pop();

		R[i] = S.top();

		S.push(i);

	}

        //计算每个位置的前缀和

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

		LL l = L[i];

		pre[i] = pre[l] + a[i] * (i - l);

	}

        //计算每个位置的后缀和

	for(int j = n; j ; j --) {

		LL r = R[j];

		suf[j] = suf[r] + a[j] * (r - j);

	}

        // 寻找合适的位置

	LL sum = pre[1] + suf[2],id = 1;

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

		if(sum < pre[i] + suf[i + 1]) {

			id = i;

			sum = pre[i] + suf[i + 1];

		}

	}

	for(int i = id - 1; i >= 1; i --) {

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

	}

        // 中间的那两个位置一定是 ok 的,我们需要从下一个开始

	for(int j = id + 2; j <= n; j ++) {

		a[j] = min(a[j - 1],a[j]);

	}

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

		cout << a[i] << " ";

	}

	cout << endl;

	return 0;

}

后记 :

优化往往是再复杂的基础上进行优化,根据某些性质,利用相应的数据结构进行优化。