题意
原题
给出\(2n\)个\(\leq m\)的数，求最优的两两配对方案
使\(n\)组\((x,y)\)的\((x+y)mod \space m\)最大值最小
\(n\leq 10^5,m \leq 10^9\)
思路
排序后大胆猜测
发现结论是: 一定存在一种最优解，使得以某个位置为界，两边分别首尾匹配，且满足左边的每一对的和都\(<m\), 右边每一对的和都\(≥m\).
证明可以看题解，大概因为每一种别的形式的解都可以转化到它，一定的等价或更优的
这样子我们就容易得到\(O(n^2)\)的枚举+判断的写法
接着发现:
- 界线越左，左边的每一对越容易变成第一类（数都变小了）。
- 界线越左，右侧的每一对越难变第二类。
- 在满足条件情况下，界线越左，最大值就越小。
- 如果左边不满足，右边一定是满足（因为右边的数都比左边大加起来任然\(<m\),右边一定全部\(<m\)）
也就是界线是可以二分的，所以就做完了
#include <bits/stdc++.h>
using std::max;
using std::min;
int n,m,a[200005],ans=0,Ans;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n*2;i++)
scanf("%d",&a[i]);
std::sort(a+1,a+2*n+1);
int l=0,r=n;
while (l<=r){
int mid=(l+r)>>1;
bool f=true;
int t=mid<<1;
int ans=0;
if (f) for(int i=t+1,j=2*n;i<j;i++,j--)
if (a[i]+a[j]<m){
f=false;break;
}
if (f){
Ans=mid;
r=mid-1;
}else l=mid+1;
}
int t=Ans*2;
for (int i=1;i<=Ans;i++) ans=max(ans,a[i]+a[t-i+1]);
for(int i=t+1,j=2*n;i<j;i++,j--) ans=max(ans,a[i]+a[j]-m);
printf("%d\n",ans);
}
后记
连二分都能写错的我。。。