前言
比赛的时候花了 [10,25] 分钟想出了如何求最大值，结果不会构造了。
如果你不知道为何WA掉，大概是因为你的权值没有开 long long。
（另外在 blog.galno.top 上的文章里 $\LaTeX$ 的渲染似乎有亿点问题……）
正文
不对的思路
省流：这是一堆废话，可以不看。
我的第一想法是先构造出一个符合题意的 B′，然后对该数组中的元素进行交换，尝试构造出权值最大的数组。但是不太可行。
于是我尝试将题目的第二个样例列了出来。
求最大权值
最大权值为：
$$B1′−B2′+B2′−B3′+B4′−B3′+B5′−B4′+B6′−B5′+B6′−B7′+B8′−B7′+B9′−B8′+B9′−B10′
化简得：
$$B1′−2B3′+2B6′−2B7′+2B9′−B10′
于是我意识到了最后的权值只与数组中的“峰”或“谷”（即 Bi′ 同时大于或小于 Bi−1′,Bi+1′(2≤i≤n−1)）以及两端有关系。显然想使权值最大，我们希望在“峰”处的数值尽量大，在“谷”处的数值尽量小。
当然数组两端的两个数有些特殊，以上述公式中的 +B1′ 举例，我们肯定希望它尽量大，但不能比其它的“峰”还大，所以如果数组中有 f 个“峰”，那么 B1′ 就应该是 B 数组中第 f+1 大的数。
好了，现在我们已经求出权值的最大值了，且这些“峰”和“谷”都可以填上数了。
构造
赛场上最后五分钟，我在代码里写了一行：
//怎么填数！！！真好，一分没得。
实际上往 B′ 中填数的这部分代码只需遵循一下规则：
从左往右填，对于第 i(1≤i≤n) 个数：
- 如果 Bi′ 已经填过数，就不用再填了。
- 如果 Ai−1<Ai，说明此时正从“谷”走向“峰”，填入 B 中未使用过的最小的数。
- 如果 Ai<Ai+1，说明此时正从“峰”走向“谷”，填入 B 中未使用过的最大的数。
贪心，不难证明其正确性。
代码
于是，我们赛时提交上去的代码仅与AC代码有 5 行之差。
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x":"<<(x)<<' '
#define dbge(x) cerr<<#x":"<<(x)<<endl
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
vi a(n+1),b(n+1);
int f=0,g=0;//记录“峰”与“谷”的数量
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
sort(b.begin()+1,b.end());
//排序后，从前取就是去最小值，从后就是取最大值
ll ans=0;//十年OI一场空
vi c(n+1);//即B'数组
for(int i=2;i<n;i++){
if(a[i-1]<a[i]&&a[i]>a[i+1]){//“峰”
ans+=2*b[n-(++f)+1];//取B中剩余数的最大值
c[i]=b[n-f+1];
}
if(a[i-1]>a[i]&&a[i]<a[i+1]){//“谷”
ans-=2*b[++g];//取B中剩余数的最小值
c[i]=b[g];
}
}
if(a[1]>a[2]){//不一定是+B'_i哦(
ans+=b[n-(++f)+1];
c[1]=b[n-f+1];
}else{
ans-=b[++g];
c[1]=b[g];
}
if(a[n]>a[n-1]){
ans+=b[n-(++f)+1];
c[n]=b[n-f+1];
}else{
ans-=b[++g];
c[n]=b[g];
}
cout<<ans<<endl;
//怎么填数！！！
//填数：
for(int i=2;i<n;i++){
if(c[i]!=0)continue;
if(a[i-1]>a[i])c[i]=b[n-(++f)+1];
else c[i]=b[++g];
}
for(int i=1;i<=n;i++)cout<<c[i]<<" \n"[i==n];
return 0;
}