题解：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

设余数 $r_i = a_i \bmod m$ 和 $s_j = b_j \bmod m$ 。
其中：

\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]

要最大化总和，我们需要最小化满足 $r_i + s_j \geq m$ 的配对数。

不妨可以得出一下策略：

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

代码如下：

CPP

#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';
	}
}

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

文章操作

相关推荐

评论

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