专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minwvp93
此快照首次捕获于
2025/12/02 09:40
3 个月前
此快照最后确认于
2025/12/02 09:40
3 个月前
查看原文
我们要求的是
∑(ai+bi)mod  m\sum(a_i + b_i) \mod m。
变形一下就是
∑aimod  m+bimod  m−[aimod  m+bimod  m≥m]×m\sum a_i \mod m + b_i \mod m - [a_i \mod m + b_i \mod m \ge m] \times m。
再变形一下就是
∑aimod  m+∑bimod  m−m⋅∑[aimod  m+bimod  m≥m]\sum a_i \mod m + \sum b_i \mod m - m \cdot \sum [a_i \mod m + b_i \mod m \ge m]。
因为 ∑aimod  m\sum a_i \mod m 和 ∑bimod  m\sum b_i \mod m 是个定值，所以我们要让答案最大即要让 ∑[aimod  m+bimod  m≥m]\sum [a_i \mod m + b_i \mod m \ge m] 最小。
考虑让最小的 aimod  ma_i \mod m 匹配最大的 bimod  mb_i \mod m。
第一种情况，若此时 aimod  m+bimod  m≥ma_i \mod m + b_i \mod m \ge m 则无论 ii 取何值均无法满足 aimod  m+bimod  m<ma_i \mod m + b_i \mod m < m。所以对于这种情况我们使用最大的 aimod  ma_i \mod m 与 最大的 bimod  mb_i \mod m 匹配一定不劣。
第二种情况，若此时 aimod  m+bimod  m<ma_i \mod m + b_i \mod m < m 那么此时直接将最小的 aia_i 与最大的 bib_i 匹配一定不劣。
匹配后将匹配的元素删去。
最后只需要统计整个序列中匹配时，情况一的数量即可求出答案。

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, m, as[N];
long long ans;
struct node{ int id, w, w2; } a[N], b[N];
inline bool cmp(node x, node y) { return x.w < y.w; };
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		ans = 0;
		cin >> n >> m;
		for(int i = 1; i <= n; ++i) {
			cin >> a[i].w;
			a[i].w %= m, a[i].id = b[i].id = i, 
			ans += a[i].w;
		}
		for(int i = 1; i <= n; ++i) {
			cin >> b[i].w;
			b[i].w2 = b[i].w, b[i].w %= m, 
			ans += b[i].w;
		}
		sort(a + 1, a + n + 1, cmp), sort(b + 1, b + n + 1, cmp);
		int mx = n;
		for(int i = 1, j = n; j; --j) {
			if(a[i].w + b[j].w >= m) 
				as[a[mx--].id] = b[j].w2, 
				ans -= m;
			else 
				as[a[i++].id] = b[j].w2;
		}
		printf("%lld\n", ans);
		for(int i = 1; i <= n; ++i) printf("%d ", as[i]);
		putchar('\n');
	}
	return 0;
}

评论

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

正在加载评论...