题解：P14029 【MX-X20-T3】「FAOI-R7」重排序列（update）

· · 题解

我们需要最大化求和式：

\sum_{i=1}^{n} \left( (a_i + b_i) \bmod m \right)

则利用模运算性质：

(a_i + b_i) \bmod m = a_i + b_i - m \times \left\lfloor \frac{a_i + b_i}{m} \right\rfloor

因此总和可表示为：

\sum a_i + \sum b_i - m \times \sum \left\lfloor \frac{a_i + b_i}{m} \right\rfloor
  1. 设余数 r_i = a_i \bmod m 和 s_j = b_j \bmod m。
  2. 其中：
\left\lfloor \frac{a_i + b_j}{m} \right\rfloor = \left\lfloor \frac{a_i}{m} \right\rfloor + \left\lfloor \frac{b_j}{m} \right\rfloor + \mathbb{I}[r_i + s_j \geq m]
  1. 要最大化总和，我们需要最小化满足 r_i + s_j \geq m 的配对数。

不妨可以得出一下策略：

  1. 将 r_i 按升序排序。
  2. 将 s_j 按降序排序。
  3. 使用双指针匹配：对每个 s_j，匹配满足 r_i \leq m-1-s_j 的最小 r_i 。
  4. 剩余元素自动满足 r_i + s_j \geq m 。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct node{
    int a,b;
}r[N],s[N];
int a[N],b[N],c[N],u[N],v[N];
bool cmp1(node a,node b){return a.a<b.a;}
bool cmp2(node a,node b){return a.a>b.a;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        for(int i=1;i<=n;i++){
            r[i]={a[i]%m,i};
            s[i]={b[i]%m,i};
        }
        sort(r+1,r+n+1,cmp1);
        sort(s+1,s+n+1,cmp2);
        int k=0,t=0,w=0;
        for(int i=1;i<=n;i++){
            if(t<n&&r[t+1].a<=m-1-s[i].a)c[r[++t].b]=b[s[i].b];
            else u[++k]=s[i].b;
        }
        for(int i=t+1;i<=n;i++)v[++w]=r[i].b;
        for(int i=1;i<=w;i++)c[v[i]]=b[u[i]];
        int c1=0,c2=0;
        for(int i=1;i<=n;i++){
            c1+=a[i]%m;
            c2+=b[i]%m;
        }
        int ans=c1+c2-m*(n-t);
        cout<<ans<<'\n';
        for(int i=1;i<=n;i++)cout<<c[i]<<' ';
        cout<<'\n';
    }
}