题目传送门
个人Blog同步链接
题意分析
证明参见”相关证明“部分。
给定 n,m 和 2n 个正整数 a_1,a_2,a_3,\cdots,a_{2n}，将其分为 n 对，两两组成一队。若 x,y 为一对，则其权值为 (x+y)\bmod m。
如果没有 \bmod m 这一个条件，那么其实很简单，将 a_1\sim a_{2n} 排序后”最大值与最小值相加求最大和“即可。
但是这里需要取模。
考虑到 0\leq a_i<m，那么就有 0\leq x+y<2m。因此，每一对 (x,y) 的权值 (x+y)\bmod m 仅仅有两种可能：x+y 和 x+y-m。
那思路就很明显了，我们要想使权值和的最大值最小，那么就让每一对 (x,y) 的权值尽可能平均。
但这如何实现呢？
将 a_1\sim a_{2n} 排序后，我们一定可以找到一个位置 p，使得 [1,p] 存在配对方案使得所有配对 (a_i,a_j) 满足 a_i+a_j<m， [p+1,2n] 存在配对方案使得所有配对 (a_i,a_j) 满足 a_i+a_j\geq m。
然后将这两段分别进行“最大值与最小值相加”即可求得最大最小权值，答案即 ：
\large \max\left(\max\limits_{i=1}^{\left\lfloor\frac p2\right\rfloor}(a_i+a_{p-i+1}),\max\limits_{i=p+1}^{\left\lfloor\frac {2n+p}2\right\rfloor}(a_i+a_{2n-i+1}-m)\right)
相关证明
约定
对于配对 $(a_i,a_j)$，若 $a_i+a_j<m$，记 $(a_i,a_j)$ 为 $x$ 型配对；若 $a_i+a_j\geq m$，记 $(a_i,a_j)$ 为 $y$ 型配对。
记 $a[l,r]$ 为序列 $a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r$。
**$a[1,p],a[p+1,2n]$ 均有可能不存在，以下暂不考虑此情况，参见引理 $5$**。
### 引理 $1
引理 1：y 型配对越多越好，即 p 越小越好。
考虑到对于所有 y 型配对 (a_i,a_j)，其权值均为 a_i+a_j-m。
又因为要求最大值最小，所以使 a_i+a_j 尽可能平均，使得能够组成的 y 型配对都组成 y 型配对，以此实现尽可能平均的目的。
引理 2
引理 2：一定存在整数 p\in[1,2n] 使得序列 a 分为两段 a[1,p],a[p+1,2n]，其中 a[1,p] 只存在 x 型配对，a[p+1,2n] 只存在 y 型配对。
证明：
我们不妨从 (a_i,a_j) 的角度来思考。
若 a_i+a_j<m，我们记 (a_i,a_j) 为 x 型配对；若 a_i+a_j\geq m，我们记 (a_i,a_j) 为 y 型配对。
那么便转化为：找到 p，使 [1,p] 均为 x 型配对，[p+1,2n] 均为 y 型配对。
考虑到一个事实：若 (a_i,a_j) 为一对，则 a_i+a_j 的值不会因为 a_i,a_j 的位置改变而改变。
因此更改顺序不影响答案。
那么我们就可以将所有 x 型配对放至 [1,p]，将所有 y 型配对放至 [p+1,2n]。
即：存在整数 p\in[1,2n] 使得序列 a 分为 a[1,p],a[p+1,2n] 且满足 a[1,p] 可被划分为 \dfrac p2 个 x 型配对，a[p+1,2n] 可被划分为 \dfrac {2n-p}{2} 个 y 型配对。
引理 3
引理 3：最终答案为 \large \max\left(\max\limits_{i=1}^{\left\lfloor\frac p2\right\rfloor}(a_i+a_{p-i+1}),\max\limits_{i=p+1}^{\left\lfloor\frac {2n+p}2\right\rfloor}(a_i+a_{2n-i+1}-m)\right)。
证明：
因为要求最大值尽可能的小，因此使和的值尽可能平均。即对于两段都采取”最大值与最小值配对“的方案。
故，正确性得证。
引理 4
引理 4：存在整数 p，使得 a[1,p] 均为 x 型配对，a[p+1,2n] 均为 y 型配对且无需改变 a 的元素顺序。
证明：
由引理 2，一定能够将 a 划分为 a[1,p],a[p+1,2n]。
考虑到 a 单调不降。
因此我们可以 n\sim1 尝试 p 值，结合引理 1，最后一个成立的 p 即为最终 p，且满足本引理。
引理 5
引理 5：当 a[1,p] 或 a[p+1,2n] 不存在时，答案仍然正确。
-
即不存在 $x$ 型配对，答案显然正确。
-
即不存在 $y$ 型配对，答案显然正确。
引理 6
引理 6：p 可以二分求得。
需要注意的是，我们是在 p 可以更小的时候尝试让 p 更小。
由于我们对 a 进行了排序，因此 a 具有单调性。
结合引理 1，本引理得证。
最终结论
（具体请参见代码注释）
结合引理 1\sim6，可得出以下最终结论。
对 a 排序以后二分 p 值直到 p 不满足 a[1,p],a[p+1,2n] 的定义即可。
最终答案即（p' 代表最后一个合法 p 值）：
\large \max\left(\max\limits_{i=1}^{\left\lfloor\frac {p'}2\right\rfloor}(a_i+a_{p'-i+1}),\max\limits_{i=p'+1}^{\left\lfloor\frac {2n+p'}2\right\rfloor}(a_i+a_{2n-i+1}-m)\right)
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5;
int n,m,ans=2147483647,a[(N<<1)+1];
//check:是否可以使p更小
bool check(int x){//就用x代替p吧......
x=(x<<1);
int pl=0;
for(int i=1;i<=x;i++){
if(a[i]+a[x-i+1]>=m)return true;//a[1,p]依然存在x型配对
pl=max(pl,a[i]+a[x-i+1]);
}
for(int i=x+1;i<=(n<<1);i++){
if(a[i]+a[(n<<1)-i+x+1]<m)return false;//已经不满足y型配对的定义
pl=max(pl,a[i]+a[(n<<1)-i+x+1]-m);
}ans=min(ans,pl);
return true;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=(n<<1);i++)scanf("%d",a+i);
sort(a+1,a+(n<<1)+1);
int l=0,r=n;//注意是二分[0,n],需要考虑不存在的情况
while(l<=r){
int mid=l+r>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}