给一个长度为 \(2n\) 的序列，要求将其两两匹配成 \(n\) 组，假设第 \(i\) 组为 \((x_i,y_i)\)，求 \(\max_{i=1}^n(x_i+y_i)\bmod m\) 的最小值，\(1\le n\le 10^5,1\le m\le 10^9,0\le a_i<m\)。
我们首先我们有：
接下来我们看几种情况：
如果我们有 \(x_1\le x_2\le x_3\le x_4\)，那么我们有这样 \(4\) 中情况：
第一种，\(x_3+x_4<m\)，那显然 \((x_1,x_4),(x_2,x_3)\) 更优。
第二种，\(x_1+x_2\ge m\)，和第一种一样。
第三种，\(\begin{cases}x_1+x_3<m\\x_2+x_4\ge m\end{cases}\)，考虑到 \(x_2+x_4-m<x_2\)，故有 \(\max\{x_1+x_3,x_2+x_4-m\}=x_1+x_3\)，而考虑到 \(\begin{cases}x_1+x_2\le x_1+x_3\\x_3+x_4-m<x_3\end{cases}\)，故有 \(\max\{x_1+x_3,x_2+x_4-m\}\ge \max\{x_1+x_2,x_3+x_4-m\}\)。所以 \((x_1,x_2),(x_3,x_4)\) 一定比 \((x_1,x_3),(x_2,x_4)\) 优。
我们再来看 \((x_1,x_4),(x_2,x_3)\) 的情况。如果有 \(\begin{cases}x_1+x_4\ge m\\x_2+x_3\ge m\end{cases}\)，那就有 \(\begin{cases}x_1+x_4-m<x1\\x_2+x_3-m<x_2\end{cases}\)，所以 \(\max\{x_1+x_4-m,x_2+x_3-m\}<x_2\le \max\{x_1+x_2,x_3+x_4-m\}\)，此时 \((x_1,x_4),(x_2,x_3)\) 的方案更优。但是如果有 \(x_1+x_4\le m\) 或是 \(x_2+x_3\le m\)，则答案将会更大。
第四种，\(\begin{cases}x_1+x_4<m\\x_2+x_3<m\\x_3+x_6\ge m\\x_4+x_5\ge m\end{cases}\)。根据前面的讨论，我们仅需比较 \((x_1,x_4),(x_2,x_3),(x_5,x_6)\) 和 \((x_1,x_2),(x_3,x_4),(x_5,x_6)\) 即可，不难发现 \(\begin{cases}x_1+x_2\le x_1+x_4\\x_3+x_6-m<x_3\le x_2+x_3\\x_4+x_5-m\le x_5+x_6-m\end{cases}\)，于是 \(\max\{x_1+x_2,x_3+x_6-m,x_4+x_5-m\}\le \max\{x_1+x_4,x_2+x_3,x_5+x_6-m\}\)。
根据第一、二、三种情况，我们发现，最终的划分结果肯定是被分成两部分，左边部分最小的匹配，次大的和次小的匹配……右边也这样匹配。其中左边所有的匹配 \((x,y)\) 都有 \(x+y<m\)，右边的匹配 \((x,y)\) 都有 \(x+y\ge m\)。
根据第四种情况，我们可以发现蓝色的匹配数越多越好，于是我们考虑二分蓝色的匹配数量，最终确定答案。
代码可以看这里。
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
namespace pufanyi {
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x << 1) + (x << 3) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
typedef long long LL;
const int maxn = 200005;
int n, m;
int aa[maxn];
inline bool check(int x) {
int lim = x << 1;
for (int l = lim + 1, r = n << 1; l < r; ++l, --r) {
if (aa[l] + aa[r] < m) {
return false;
}
}
return true;
}
int Main() {
read(n), read(m);
for (int i = 1; i <= n << 1; ++i) {
read(aa[i]);
}
sort(aa + 1, aa + (n << 1) + 1);
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
int ans = 0;
int lim = l << 1;
for (int l = 1, r = lim; l < r; ++l, --r) {
ans = max(ans, (aa[l] + aa[r]) % m);
}
for (int l = lim + 1, r = n << 1; l < r; ++l, --r) {
ans = max(ans, (aa[l] + aa[r]) % m);
}
writeln(ans);
return 0;
}
}
int main() {
return pufanyi::Main();
}