题解：AT_arc201_d [ARC201D] Match, Mod, Minimize

· · 题解

先将加法取模转换成减法，即 \max_{i=1}^N ( B_i-(-A_i) \bmod M )。设 (-A_i) \bmod M 为 A_i '，按照 B_i 大小分类：

(B_i-A_i') \bmod M=\begin{cases} B_i-A_i' & B_i \ge A_i'\\ M+ B_i-A_i' & B_i < A_i' \end{cases}

也就是说，我们可以将 B 数列中部分数加上 M，排序，使每个数对应的 A' 数列的数小于等于自己，答案就是最大差。设要对 k 个数加上 M，简单调整发现，对 B 数列前 k 小的数加，更容易使条件成立，也使结果更优。二分答案即可。

/*

        2025.12.2

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define R register
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=1000005,inf=0x3f3f3f3f,mod=998244353;
int n,m,a[MAXN],b[MAXN],c[MAXN];
inline int gt(int x){return (x%m+m)%m;}
int check(int x){
    int ans=0;
    for(int i=1;i<=x;i++)c[i+n-x]=b[i]+m;
    for(int i=x+1;i<=n;i++)c[i-x]=b[i];
    for(int i=1;i<=n;i++){
        if(a[i]>c[i])return -1;
        ans=max(ans,c[i]-a[i]);
    }
    return ans;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]=gt(-a[i]);
    for(int i=1;i<=n;i++)cin>>b[i];
    sort(a+1,a+1+n);sort(b+1,b+1+n);
    int l=0,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)==-1)l=mid+1;
        else r=mid;
    }
    cout<<check(l)<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}