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

解题思路

贪心。

先把两个数组的数字、除

m

的余数、当前的位置

i

都存到一个结构体里面，对

a

按余数从大到小、

b

按余数从小到大排序，以便后续操作。

然后再贪心。把

b

中的最小的余数在

a

中一个一个试，若它们两个加起来小于

m

，则成功配对。再把

b

中的第二小的余数在

a

中接着试……这样，就可以尽可能地减少模

m

对答案造成的影响。

对于不满足条件的数字，任意两两配对即可。可以证明这时两个数加起来大于等于

m

、小于

2\times m

，所以不管如何模

m

后都要减少

m

。然后，记录减少

m

的数量

ss

，计算答案时直接减

ss\times m

即可。

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

Code

CPP

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

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

文章操作

解题思路

Code

相关推荐

评论

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