首先对于两个排列 $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$
那么容易想到贪心，每次都先加得比较大，最后快超过的时候再加一个比较小的
容易证明这个显然是最优的，因为一开始就加大的之后的选择就有更多空间（有更多比较小的值可以增加）
不然到时候还剩下一些时间，发现增加的量都很大那么就没法加了
（可能看代码更容易理解？）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7; int n,ans[N]; ll m; int main() { n=read(),m=read(); ll mx=m; for(int i=1;i<=n;i++) ans[i]=i,m-=i; if(m<0) { printf("-1 "); return 0; } for(int i=1;i<=n/2;i++) { int now=(n-i+1)-i; if(m<=now) { swap( ans[ n-i+1 - (now-m) ] , ans[i] ); // 显然 n-i-1 - (now-m) > i，代入一下 now=n-2i+1 即可 m=0; break; } swap(ans[n-i+1],ans[i]); m-=now; } printf("%lld ",mx-m); for(int i=1;i<=n;i++) printf("%d ",i); puts(""); for(int i=1;i<=n;i++) printf("%d ",ans[i]); puts(""); return 0; }