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

cengzh · 2025-09-14 16:38:09 · 题解

该做法与第一篇题解略有不同。

已知 (a+b) \bmod m = (a \bmod m) + (b \bmod m ) \bmod m，我们将 a,b 序列中所有数对 m 取模，那么 a_i+b_i 的值域为 [0,2m]。

理想情况下，对于所有 i 有 a_i+b_i<m，那么和为 \sum^n_i (a_i+b_i)。但显然我们可能会有某些位置 i 有 a_i+b_i \ge m，此时贡献变成了 a_i+b_i-m。对比理想状况，位置 i 产生的贡献减少了 (a_i+b_i)-(a_i+b_i-m) = m，m 是给定常数，问题就转化成如何排列使得 a+b \ge m 的情况最少。

将 a 降序排序，b 升序排序，a_i 在递减过程中，b 中满足 a_i+b_j<m 的区间会向右扩展，我们不难发现此时 a_i 去匹配最小的 b_j 是最优的。如果 a_i 怎么匹配都匹配不到 a_i+a_j<m，那就只能去和最大的 b_j 匹配，将更小的 b_j 留给后面的数。

时间复杂度 O(n \log n)。

# include <bits/stdc++.h>

using namespace std;

struct arr{
    long long v;
    long long new_v;
    int idx;
};
arr arr1[200005];
arr arr2[200005];

bool cmp1(arr a,arr b) {return a.new_v > b.new_v;}
bool cmp2(arr a,arr b) {return a.new_v < b.new_v;}
bool cmp3(arr a,arr b) {return a.idx < b.idx;}

void solve()
{
    int n,m;
    scanf ("%d %d",&n,&m);

    for (int i=0;i<n;i++) scanf ("%lld",&arr1[i].v);
    for (int i=0;i<n;i++) scanf ("%lld",&arr2[i].v);
    for (int i=0;i<n;i++) 
    {
        arr1[i].idx = i;
        arr2[i].idx = i;
        arr1[i].new_v=arr1[i].v%m;
        arr2[i].new_v=arr2[i].v%m;
    }

    sort(arr1,arr1+n,cmp1);
    sort(arr2,arr2+n,cmp2);

    long long ans=0;
    int l=0,r=n-1;
    for (int i=0;i<n;i++)
    {
        if (arr1[i].new_v + arr2[l].new_v >= m) 
        {
            ans += (arr1[i].new_v + arr2[r].new_v) % m;
            arr2[r--].idx = arr1[i].idx;    
        }
        else
        {
            ans += (arr1[i].new_v + arr2[l].new_v) % m;
            arr2[l++].idx = arr1[i].idx;
        }
    }

    sort(arr2,arr2+n,cmp3);

    printf ("%lld\n",ans);
    for (int i=0;i<n;i++) printf ("%lld ",arr2[i].v);
    printf ("\n");
    return ;
}

int main (void)
{
    int T;
    scanf ("%d",&T);

    while (T--)
    {
        solve();    
    }
    return 0;
}