AGC032E modulo pairing

题意

原题
给出\(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);
} 

后记

连二分都能写错的我。。。