0%

CF622div2C(hard&easy)解题报告

摘要:数据结构贪心题

C. Skyscrapers

题面(easy)

题面(hard)

题目分析

简单说下题意,给定一个序列m,表示每个位置的数最大是多少,现在要构造出一个序列a,使得每个数不会两边都有高于它的数,且最大化数的和.

简单版的$n \leq 1000$,复杂版的$n \leq 500000$.

先讲一下简单版的,可以发现构造出的数列一定是呈一个山峰状,因为题目的要求,不可能存在谷底,所以我们可以暴力枚举山峰的位置,两边分别用单调栈来维护,能取到最大的最大的就直接取最大,不然就取和上一个数一样的,还有一个奇技淫巧,因为数字太大了,比较哪个答案更优时会爆long long,所以把每个数除以10000用double存,这还真过了.

这样做是$O(n^2)$的,复杂版的过不去,考虑其他方法.

可以发现,我们可以像找出m序列中最小的数,因为这个数是一定会让它的左边或是右边全部等于它的,不然就产生了谷底,但是具体是让右边或是左边等于它是不确定的,所以我们使用递归进行贪心,取答案最优的那一边.

每次找到最小数执行上述操作后把序列缩短至没有被赋值的那一边,视为一个新的序列再次操作,直到序列长度为1.

所以这里就涉及到一个rmq问题,用线段树或ST表均可解决.

代码

easy

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cctype"
#include "cmath"
#include "algorithm"
#include "iomanip"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%d\n",x)
const lxl maxn=1010;
lxl n;
double min_=INF;
lxl a[maxn],s1[maxn],s2[maxn],ans[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)a[i]=read();
for(R int i(1);i<=n;++i)
{
double tmp;
s1[0]=s2[0]=tmp=0;
for(R int j(i-1);j;--j)
{
if(!s1[0])s1[++s1[0]]=a[j];
else
{
if(a[j]<=s1[s1[0]])
{
s1[++s1[0]]=a[j];
// if(i==6)debug(a[j]);
}
else
{
s1[s1[0]+1]=s1[s1[0]],tmp+=(double)(a[j]-s1[s1[0]])/10000,++s1[0];
// if(i==6)debug(tmp);
}
}
}
for(R int j(i);j<=n;++j)
{
if(!s2[0])s2[++s2[0]]=a[j];
else
{
if(a[j]<=s2[s2[0]])
{
// if(i==6)debug(a[j]);
s2[++s2[0]]=a[j];
}
else
{
s2[s2[0]+1]=s2[s2[0]],tmp+=(double)(a[j]-s2[s2[0]])/10000,++s2[0];
// if(i==6)debug(a[j]),debug(s2[s2[0]]);
}
}
}
if(tmp<min_)
{
min_=tmp,ans[0]=0;
for(R int j(s1[0]);j;--j)ans[++ans[0]]=s1[j];
for(R int j(1);j<=s2[0];++j)ans[++ans[0]]=s2[j];
}
}
for(R int i(1);i<=ans[0];++i)printf("%lld ",ans[i]);
printf("\n");
return 0;
}
/*
input:
6
4 1 2 3 2 1
output:
1 1 2 3 2 1
*/

hard

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
65
66
67
68
69
70
71
#include "iostream"
#include "cstring"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "cstdio"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=500010;
lxl n;
lxl a[maxn],st[maxn][20],lg[maxn],ans[maxn];
double pre[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline void ST()
{
lg[0]=-1;
for(R int i(1);i<=n;++i)lg[i]=lg[i>>1]+1;
for(R int i(1);i<=n;++i)st[i][0]=i;
for(R int j(1);j<20;++j)
for(R int i(1);i+(1<<j)-1<=n;++i)
st[i][j]=a[st[i][j-1]]<=a[st[i+(1<<(j-1))][j-1]]?st[i][j-1]:st[i+(1<<(j-1))][j-1];
}
inline lxl STQuery(lxl l,lxl r)
{
lxl t=lg[r-l+1];
return a[st[l][t]]<=a[st[r-(1<<t)+1][t]]?st[l][t]:st[r-(1<<t)+1][t];
}
lxl dfs(lxl l,lxl r)
{
if(l>r)return 0;
if(l==r){return ans[l]=a[l];}
lxl now=STQuery(l,r);
lxl left=(now-l+1)*a[now]+dfs(now+1,r);
lxl right=(r-now+1)*a[now]+dfs(l,now-1);
if(left>right)
{
for(R int i(l);i<=now;++i)ans[i]=a[now];
return left;
}
else
{
for(R int i(now);i<=r;++i)ans[i]=a[now];
return right;
}
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)a[i]=read();
ST();
dfs(1,n);
for(R int i(1);i<=n;++i)printf("%lld ",ans[i]);
printf("\n");
return 0;
}