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

· · 题解

思路分析

首先，每个数可以造成的贡献最大为它 \mod m 的值，所以我们可以把数列就看做是每个数 \mod m 的值。对于取模之后的每个数对，如果 a+b\ge m，则他们的贡献为 a+b-m，否则他们的贡献为 a+b，所以我们需要尽量多地匹配 a+b<m。

考虑实现，先对这两个取模之后的序列排序，对于 a 中的每个元素从大到小匹配 b 中的元素，由于 a 序列单调不降，所以当 a 变大的时候 b 一定会变小，只需要用两个指针分别正向和反向扫描一遍，\mathcal{O}(n) 进行匹配，最后再将剩余的元素任意匹配。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=200005;
ll T, n, b[N], mod, vis[N], t[N];
struct Node{
    ll pos, val;
    friend bool operator<(Node a, Node b){
        return a.val%mod<b.val%mod;
    }
}a[N];
bool cmp(ll a, ll b){
    return a%mod<b%mod;
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&mod);
        for(ll i=1;i<=n;i++){
            scanf("%lld",&a[i].val);
            a[i].pos=i;
        }
        for(ll i=1;i<=n;i++) scanf("%lld",&b[i]);
        sort(a+1,a+n+1);
        sort(b+1,b+n+1,cmp);
        memset(vis,0,sizeof(vis));
        memset(t,0,sizeof(t));
        ll ans=0;
        for(ll i=1,j=n;i<=n;i++,j--){
            while(a[i].val%mod+b[j]%mod>=mod&&j>=1) j--;
            if(j==0) break;
            t[a[i].pos]=j, vis[j]=1, ans+=a[i].val%mod+b[j]%mod;
        }
        for(ll i=1,j=1;i<=n;i++){
            if(t[a[i].pos]>0) continue;
            while(vis[j]==1&&j<=n) j++;
            t[a[i].pos]=j, ans+=(a[i].val%mod+b[j]%mod)%mod, j++;
        }
        printf("%lld\n",ans);
        for(ll i=1;i<=n;i++) printf("%lld ",b[t[i]]);
        printf("\n");
    }
    return 0;
}

代码总复杂度为 \mathcal{O}(Tn\log n)，可以通过这道题。