Codeforces Round #622(Div 2) C1. Skyscrapers (easy version)

题目链接:

题目描述:

有一行数,使得整个序列满足 先递增在递减(或者只递增,或者只递减) ,每个位置上的数可以改变,但是最大不能超过原来的值。

最后找到满足这样的序列并且满足 这种方案 所有数加起来 和 是最大的。

考察点 :

贪心,对数据范围的掌握程度,计算每次加数时有可能会 爆 int

析题得侃:

比赛的时候看到这道题直接找了 最大值,然后以最大值为中心向两侧递减,交了一发, WA

后来想到可能会有重复的最大值,因为每个值并不是唯一出现的,这就遇到麻烦了,到底我从

那里开始递减才是最优的结果呢？

赛后才醒过神来:

看一下这个 easy version 的数据范围, 1000

我们完全可以用双循环把每个数都当作中间数进行尝试一下,这样去寻找最大值,进而找到

合适的范围,时间复杂度 O（n^2）

优化版:

Hard Version

Code：

#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];

// 用来记录以某个位置为中间的总和

LL cnt[maxn];

LL res = 0;

int n;

int main(void) {

	scanf("%d",&n);

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

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

	}

	LL mid = 0;

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

		mid = a[i];

		cnt[i] += a[i];

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

			mid = min(mid,a[j]);

			cnt[i] += mid;

		}

		mid = a[i];

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

			mid = min(mid,a[j]);

			cnt[i] += mid;

		}

		res = max(res,cnt[i]);

	}

        // 寻找合适的位置

	int pos = 0;

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

		if(res == cnt[i]) {

			pos = i;

			break;

		}

	}

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

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

	}

	for(int j = pos + 1; 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;

}

后记:

一定要多看看数据范围,一定要多看看

多想想,会不会有重复的值。

巴特西

Codeforces Round #622(Div 2) C1. Skyscrapers (easy version)

题目链接:

题目描述:

考察点 :

析题得侃:

优化版:

Code：

后记:

最新文章

热门文章