专栏文章

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

sson_son
AT_abc416_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopmx1z
此快照首次捕获于
2025/12/02 23:05
3 个月前
此快照最后确认于
2025/12/02 23:05
3 个月前
查看原文

题面大意

给定两个长度都为 NN 的数组 ABAB 和一个整数 MM，让你重新排列 AA，使得 ∑i=1N((Ai+Bi)mod  M)\sum\limits_{i=1}^N((A_i+B_i) \mod M) 最小，并输出这个数。
其中 1≤N≤3×1051 \le N \le 3 \times 10^{5}，1≤M≤1091 \le M \le 10^{9} 且 AA 和 BB 中的每个元素都小于 MM。
（10510^{5} 次多测，∑N≤3×105\sum N \le 3 \times 10^{5}）

思路

根据 AA 和 BB 中的每个元素都小于 MM 这个条件可以推出 Ai+BiA_i+B_i 是小于 2×M2 \times M 的。
所以在模 MM 的时候，每次 Ai+BiA_i+B_i 都会有两种情况：
第一种：Ai+Bi<MA_i+B_i < M 跟直接加没区别。
第二种：Ai+Bi≥MA_i+B_i \ge M 这样便会在之前的答案上减掉一个 MM。
可以很清楚的发现，第二种是完全优于第一种的，所以我们要尽可能多的产生第二种。
贪心的考虑，给每个 BiB_i 配最小能使得和大于等于 MM 的 AiA_i，最后剩实在配不了的。
将两个数组排个序，因为有单调性了所以后面可以直接双指针做。

AC CODE：

CPP
#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);
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...