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

qkj_qwq · 2025-09-13 21:48:35 · 题解

解题思路

贪心。

先把两个数组的数字、除 m 的余数、当前的位置 i 都存到一个结构体里面，对 a 按余数从大到小、b 按余数从小到大排序，以便后续操作。

然后再贪心。把 b 中的最小的余数在 a 中一个一个试，若它们两个加起来小于 m，则成功配对。再把 b 中的第二小的余数在 a 中接着试……这样，就可以尽可能地减少模 m 对答案造成的影响。

对于不满足条件的数字，任意两两配对即可。可以证明这时两个数加起来大于等于 m、小于 2\times m，所以不管如何模 m 后都要减少 m。然后，记录减少 m 的数量 ss，计算答案时直接减 ss\times m 即可。

注意输出方案时要按原来的顺序（即用数组记录一下）。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int x,y,z;
}a[200010],b[200010];
int ans[200010];
bool cmp (node xx,node yy){return xx.y>yy.y;}
bool cmpp(node xx,node yy){return xx.y<yy.y;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,noww,now=1,s=0,ss=0;
        cin>>n>>m;noww=n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].x;
            s+=(a[i].y=a[i].x%m);
            a[i].z=i;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>b[i].x;
            s+=(b[i].y=b[i].x%m);
            b[i].z=i;
        }
        sort(a+1,a+n+1,cmp);
        sort(b+1,b+n+1,cmpp);
        for(int i=1;i<=n;i++)
            if(a[i].y+b[now].y>=m)
            {
                ans[a[i].z]=b[noww--].x;
                ss++;
            }
            else ans[a[i].z]=b[now++].x;
        cout<<s-ss*m<<'\n';
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<' ';
        cout<<'\n';
    }
    return 0;
}