【题解】AT4520：[AGC032E] Modulo Pairing

原题传送门
首先想到的当然是二分答案+贪心
但是正解二分的并不是答案

结论：最终的正确答案一定存在一个分界点，满足

蓝线表示$x+y<M$
红线表示$x+y>=M$

给出证明

情况1：

任意两个数加起来都$<M$的情况，Ⅰ最优
令从左到右分别为$a<b<c<d$
计算出三种方案的价值
Ⅰ:$max(a+d,b+c)$
Ⅱ:$max(a+b,c+d)=c+d>a+d,b+c,即Ⅱ>Ⅰ$
Ⅲ:$max(a+c,b+d)=b+d>a+d,b+c,即Ⅲ>Ⅰ$
证毕

情况2：
任意两个数加起来都$>=M$的情况，Ⅰ最优
在证明之前先要发现，因为每个数$<M$
所以对于任意$x+y>=M,x+y-M<min(x,y)$

Ⅰ:$max(a+d,b+c)-M$
Ⅱ:$max(a+b,c+d)-M$
Ⅲ:$max(a+c,b+d)-M$
其实变成了情况1的证明

情况3：

Ⅰ:$max(a+d-M,b+c)=b+c$
Ⅱ:$max(a+b,c+d-M)=max(a+b,e)(e为<c的一个数)$
Ⅱ$<$Ⅰ

情况4：

Ⅰ:$max(b+d-M,a+c)=a+c$
Ⅱ:$max(a+b,c+d-M)=max(a+b,e)(e为<c的一个数)$
Ⅱ$<$Ⅰ

情况5：

Ⅰ:$max(b+c-M,a+d)=a+d$
Ⅱ:$max(a+b,c+d-M)=max(a+b,e)(e为<c的一个数)$
Ⅱ$<$Ⅰ

所有情况都罗列了
结论就证明好了

所以正确答案一定满足最开始说的那种情况，分界点左边全是蓝线，最大最小相连，次大次小相连……，右边全是红线，最大最小相连，次大次小相连……
然后分界点是越小越好，合法的分界点越小，左右两边的权值越小，同时的左边越可能满足蓝线
所以答案就一定是合法的最小的分界点

二分分界点，找到最小的就行了

Code：

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int a[maxn], n, m;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool check(int mid){
	for (int i = mid + 1, j = n; i <= j; ++i, --j) if (a[i] + a[j] < m) return 0;
	return 1;
}

int main(){
	n = read() << 1, m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	sort(a + 1, a + 1 + n);
	int l = 0, r = n >> 1, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid << 1)) ans = mid << 1, r = mid - 1; else l = mid + 1;
	}
	int sum = 0;
	for (int i = 1, j = ans; i <= j; ++i, --j) sum = max(sum, a[i] + a[j]);
	for (int i = ans + 1, j = n; i <= j; ++i, --j) sum = max(sum, a[i] + a[j] - m);
	printf("%d\n", sum);
	return 0;
}