如有错误，请留言提醒，不要坑到小朋友
Description
Slavko‘s院子的围墙，由N块高度不同的木板组成。
每块木板的高度用一个小于1000000000的正整数表示，“高度差的和”指的是，相邻两块木板的高度差之和。
Mirko也买来了N块木板，打算用这些木板做一个围墙，但他不知道怎么安排这些木板的放置顺序，他希望他的围墙能与Slavko家的围墙“相似”，另外，Mirko希望他的围墙“高度差的和”尽可能大。
所谓“相似”，是指相邻两块木板之间的高度关系相同，比如Slavko的围墙，第i块木板高度大于（小于）第i+1块木板，那么Mirko的围墙，第i块木板高度也要大于（小于）第i+1块木板的高度。
现在，已知Slavko’s 围墙每块木板的高度，以及每块Mirko买来的木板的高度，请你帮Mirko安排这些木板的放置顺序，使得“高度差的和”尽可能大，且与Slavko的围墙“相似”。
输入：
第一行：整数N（2<=N<=3000000），表示木板的数量
第二行：N个不同的整数，表示Slavko‘s围墙
第三行：N个不同的整数，表示Mirko买来的木板
输出：
第一行：Mirko的围墙，“高度差的和”的最大值
第二行：按顺序输出Mirko的围墙，每块木板的高度
Input
4
5 7 4 9
1 2 3 4
Output
7
2 4 1 3
首先，这题我们可以看出Slavko的围墙大概是这样的
红点指左右的点的高度均低于或高于此点的点
我们可以发现第一个答案只与红点有关
因为二个红点之间的点的高度差的绝对值之和==二个红点高度差的绝对值
所以我们用贪心思想，使红点的高度差尽量大
把红点分为0,1两类
0类红点取没有取过的最矮围墙
1类红点取没有取过的最高围墙
我们让0类红点尽量小
让1类红点尽量大，最后模拟得出最优解；
ps：不能把最小（大）的围墙用在最边上的红点上
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 3100000
using namespace std;
int dd[maxn][2],a[maxn],b[maxn],tot,c[maxn][2],n;
long long ans;
inline int read(){
int tmp=0;char ch;
while(ch=getchar())if('0'<=ch&&ch<='9')break;
for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
return tmp;
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
dd[++tot][0]=1;
dd[tot][1]=a[2]>a[1]?0:1;
for(int i=2;i<n;i++)if((a[i+1]<a[i])!=dd[tot][1]){
dd[++tot][0]=i;
dd[tot][1]=a[i+1]>a[i]?0:1;
}
dd[++tot][0]=n;
dd[tot][1]=a[n]>a[n-1]?1:0;
sort(b+1,b+n+1);
int l=1,r=n;
bool kk;
for(int i=2;i<=tot-1;i++)c[dd[i][0]][0]=(c[dd[i][0]][1]=dd[i][1])?b[r--]:b[l++];
c[dd[1][0]][0]=(c[dd[1][0]][1]=dd[1][1])?b[r--]:b[l++];
c[dd[tot][0]][0]=(c[dd[tot][0]][1]=dd[tot][1])?b[r--]:b[l++];
for(int i=1;i<=n;i++)if(!c[i][0]){
c[i][0]=!kk?b[l++]:b[r--];
}else kk=c[i][1];
for(int i=2;i<=n;i++)ans+=1LL*abs(c[i][0]-c[i-1][0]);
printf("%I64d\n",ans);
for(int i=1;i<=n;i++)printf("%d ",c[i][0]);
// system("pause");
}