（实话实说，不明白为什么要评紫，因为做题不需要完全严谨证明。就算加上证明难度也最多蓝。模拟赛场切，却根本不会证明……建议评绿）
题意分析
证明参见”相关证明“部分。
给定 $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_1,a_2,a_3,\cdots,a_{2n}$ 均已排序，且单调不降。
对于配对 $(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]$ 不存在时，答案仍然正确。
-
$a[1,p]$ 不存在。
即不存在 $x$ 型配对，答案显然正确。
-
$a[p+1,2n]$ 不存在。
即不存在 $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 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//#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;
}
