首先对于两个排列 $A,B$ 我们可以把 $A$ 从小到大排序并把 $B$ 重新和 $A$ 一一对应
显然这样不会影响 $\sum_{i=1}^{n}max(A_i,B_i)$ 的值
所以直接把第一个排列固定为 $1,2,3,...,n$
然后考虑第二个排列 $B$ 怎么排比较好
首先最少的时间一定就是 $B_i=i$ 的情况
然后考虑让时间变大，容易想到把 $B_1$ 和 $B_n$ 交换，变成 $n,2,3,...,n-1,1$
那么时间增加了 $n-1$，一直操作最后 $B$ 就变成 $n,n-1,n-2,...,3,2,1$
那么容易想到贪心，每次都先加得比较大，最后快超过的时候再加一个比较小的
容易证明这个显然是最优的，因为一开始就加大的之后的选择就有更多空间（有更多比较小的值可以增加）
不然到时候还剩下一些时间，发现增加的量都很大那么就没法加了
（可能看代码更容易理解？）
1#include<iostream> 2#include<cstdio> 3#include<algorithm> 4#include<cstring> 5#include<cmath> 6using namespace std; 7typedef long long ll; 8inline ll read() 9{ 10 ll x=0,f=1; char ch=getchar(); 11 while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } 12 while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } 13 return x*f; 14} 15const int N=1e6+7; 16int n,ans[N]; 17ll m; 18int main() 19{ 20 n=read(),m=read(); ll mx=m; 21 for(int i=1;i<=n;i++) 22 ans[i]=i,m-=i; 23 if(m<0) { printf("-1\n"); return 0; } 24 for(int i=1;i<=n/2;i++) 25 { 26 int now=(n-i+1)-i; 27 if(m<=now) 28 { 29 swap( ans[ n-i+1 - (now-m) ] , ans[i] ); 30 // 显然 n-i-1 - (now-m) > i，代入一下 now=n-2i+1 即可 31 m=0; break; 32 } 33 swap(ans[n-i+1],ans[i]); m-=now; 34 } 35 printf("%lld\n",mx-m); 36 for(int i=1;i<=n;i++) printf("%d ",i); puts(""); 37 for(int i=1;i<=n;i++) printf("%d ",ans[i]); puts(""); 38 return 0; 39}