题解：P14029 【MX-X20-T3】「FAOI-R7」重排序列（update）
chrisgr
·
·
题解
我们要求的是
变形一下就是
$\sum a_i \mod m + b_i \mod m - [a_i \mod m + b_i \mod m \ge m] \times m$。
再变形一下就是
$\sum a_i \mod m + \sum b_i \mod m - m \cdot \sum [a_i \mod m + b_i \mod m \ge m]$。
因为 $\sum a_i \mod m$ 和 $\sum b_i \mod m$ 是个定值，所以我们要让答案最大即要让 $\sum [a_i \mod m + b_i \mod m \ge m]$ 最小。
考虑让最小的 $a_i \mod m$ 匹配最大的 $b_i \mod m$。
第一种情况，若此时 $a_i \mod m + b_i \mod m \ge m$ 则无论 $i$ 取何值均无法满足 $a_i \mod m + b_i \mod m < m$。所以对于这种情况我们使用最大的 $a_i \mod m$ 与 最大的 $b_i \mod m$ 匹配一定不劣。
第二种情况，若此时 $a_i \mod m + b_i \mod m < m$ 那么此时直接将最小的 $a_i$ 与最大的 $b_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;
}
```