BZOJ 3180 ograda

贪心

贡献只跟拐点有关，让山峰尽可能高，山谷尽可能深即可

注意两端是半峰半谷，还有山坡的走向

#include <cstdio>
#include <cassert>
#include <algorithm>

using std::sort;

const int MAXN=300111;

int N;
bool Mid[MAXN];
long long Std[MAXN], Num[MAXN];
long long Ans[MAXN], ANS;
int Hp[MAXN], Hcnt, Lp[MAXN], Lcnt;
int L, R;

int main(){
	
	scanf("%d", &N);
	for(int i=1;i<=N;++i)
		scanf("%lld", &Std[i]);
	for(int i=1;i<=N;++i)
		scanf("%lld", &Num[i]);
	
	if(N==1){
		puts("0");
		printf("%d
", Num[1]);
		return 0;
	}
	
	sort(Num+1, Num+N+1);
	
	/*
	Std[0]=Std[1];Std[N+1]=Std[N];
	for(int i=1;i<=N;++i){
		Mid[i]=true;
		if(Std[i-1]<=Std[i] && Std[i]>=Std[i+1])	{Hp[++Hcnt]=i;Mid[i]=false;}
		if(Std[i-1]>=Std[i] && Std[i]<=Std[i+1])	{Lp[++Lcnt]=i;Mid[i]=false;}
	}
	
	sort(Num+1, Num+N+1);
	
	L=1;R=N;
	for(int i=1;i<=Lcnt;++i)	Ans[Lp[i]]=Num[L++];
	for(int i=1;i<=Hcnt;++i)	Ans[Hp[i]]=Num[R--];
	for(int i=1;i<=N;++i)	if(Mid[i])	Ans[i]=Num[L++];
	assert(R+1==L);
	
	*/
	
	Std[0]=Std[1];Std[N+1]=Std[N];
	for(int i=1;i<=N;++i){
		Mid[i]=true;
		if(Std[i-1]<Std[i] && Std[i]>Std[i+1])	{Hp[++Hcnt]=i;Mid[i]=false;}
		if(Std[i-1]>Std[i] && Std[i]<Std[i+1])	{Lp[++Lcnt]=i;Mid[i]=false;}
	}
	
	L=1;R=N;
	for(int i=1;i<=Lcnt;++i)	Ans[Lp[i]]=Num[L++];
	for(int i=1;i<=Hcnt;++i)	Ans[Hp[i]]=Num[R--];
	
	if(Std[1]<Std[2])	Ans[1]=Num[L++];
	else	Ans[1]=Num[R--];
	if(Std[N-1]<Std[N])	Ans[N]=Num[R--];
	else	Ans[N]=Num[L++];
	
	for(int i=2;i<N;++i){
		if(!Mid[i])	continue;
		if(Std[i]<Std[i+1])	Ans[i]=Num[L++];
		if(Std[i]>Std[i+1])	Ans[i]=Num[R--];
	}
	
	assert(R+1==L);
	
	ANS=0LL;
	for(int i=1;i<N;++i)	ANS+=labs(Ans[i]-Ans[i+1]);
	
	printf("%lld
", ANS);
	for(int i=1;i<=N;++i)	printf("%lld ", Ans[i]);
	puts("");
	
	return 0;
}

/*
4
5 7 4 9
1 2 3 4

7
2 4 1 3

*/