专栏文章

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

AAamumatematiikka
P14029题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwvz6k
此快照首次捕获于
2025/12/02 09:40
3 个月前
此快照最后确认于
2025/12/02 09:40
3 个月前
查看原文

思路分析

首先，每个数可以造成的贡献最大为它 mod  m\mod m 的值，所以我们可以把数列就看做是每个数 mod  m\mod m 的值。对于取模之后的每个数对，如果 a+b≥ma+b\ge m，则他们的贡献为 a+b−ma+b-m，否则他们的贡献为 a+ba+b，所以我们需要尽量多地匹配 a+b<ma+b<m。
考虑实现，先对这两个取模之后的序列排序，对于 aa 中的每个元素从大到小匹配 bb 中的元素，由于 aa 序列单调不降，所以当 aa 变大的时候 bb 一定会变小，只需要用两个指针分别正向和反向扫描一遍，O(n)\mathcal{O}(n) 进行匹配，最后再将剩余的元素任意匹配。

代码实现

CPP
#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;
}
代码总复杂度为 O(Tnlog⁡n)\mathcal{O}(Tn\log n)，可以通过这道题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...