题解：AT_abc416_d [ABC416D] Match, Mod, Minimize 2

· · 题解

题面大意

给定两个长度都为 N 的数组 AB 和一个整数 M，让你重新排列 A，使得 \sum\limits_{i=1}^N((A_i+B_i) \mod M) 最小，并输出这个数。

其中 1 \le N \le 3 \times 10^{5}，1 \le M \le 10^{9} 且 A 和 B 中的每个元素都小于 M。

（10^{5} 次多测，\sum N \le 3 \times 10^{5}）

思路

根据 A 和 B 中的每个元素都小于 M 这个条件可以推出 A_i+B_i 是小于 2 \times M 的。

所以在模 M 的时候，每次 A_i+B_i 都会有两种情况：

第一种：A_i+B_i < M 跟直接加没区别。

第二种：A_i+B_i \ge M 这样便会在之前的答案上减掉一个 M。

可以很清楚的发现，第二种是完全优于第一种的，所以我们要尽可能多的产生第二种。

贪心的考虑，给每个 B_i 配最小能使得和大于等于 M 的 A_i，最后剩实在配不了的。

将两个数组排个序，因为有单调性了所以后面可以直接双指针做。

AC CODE：

#include<bits/stdc++.h>
using namespace std;
long long _,n,m,a[300005],b[300005],ans;
inline bool cmp(long long x,long long y){
    return x>y;
}
int main(){
    scanf("%lld",&_);
    while(_--){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%lld",&b[i]);
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1,cmp);
        long long tp=1;
        ans=0;
        for(int i=1;i<=n;i++){
            while(b[i]+a[tp]<m && tp<=n)tp++;
            if(tp==n+1)break;
            ans+=(b[i]+a[tp])%m;
            b[i]=a[tp]=0;
            tp++;
        }
        for(int i=1;i<=n;i++){
            ans+=a[i]+b[i];
        }
        printf("%lld\n",ans);
    }
}