题目链接:
C1. Skyscrapers (easy version)
题目描述:
有一行数,使得整个序列满足 先递增在递减(或者只递增,或者只递减) ,每个位置上的数可以改变,但是最大不能超过原来的值。
最后找到满足这样的序列并且满足 这种方案 所有数加起来 和 是最大的。
考察点 :
贪心,对数据范围的掌握程度,计算每次加数时有可能会 爆 int
析题得侃:
比赛的时候看到这道题直接找了 最大值,然后以最大值为中心向两侧递减,交了一发, WA
后来想到可能会有重复的最大值,因为每个值并不是唯一出现的,这就遇到麻烦了,到底我从
那里开始递减才是最优的结果呢？
赛后才醒过神来:
看一下这个 easy version 的数据范围, 1000
我们完全可以用双循环把每个数都当作中间数进行尝试一下,这样去寻找最大值,进而找到
合适的范围,时间复杂度 O（n^2）
优化版:
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;
}
后记:
一定要多看看数据范围,一定要多看看
多想想,会不会有重复的值。