题目：找朋友
给定两个长度均为 N 的数组 A、B，以及模数 M。已知：
0 <= A[i], B[i] < M
要求找到一个排列 p，使下式取得最小值：
S = sum((A[i] + B[p[i]]) mod M)
思路分析
1. 展开取模运算
由于 A[i] 和 B[i] 都小于 M，两数之和一定满足：
0 <= A[i] + B[p[i]] < 2M
所以每一项只有两种情况：
(A[i] + B[p[i]]) mod M
= A[i] + B[p[i]] 当 A[i] + B[p[i]] < M
= A[i] + B[p[i]] - M 当 A[i] + B[p[i]] >= M
设满足 A[i] + B[p[i]] >= M 的配对数量为 K，那么：
S = sum(A) + sum(B) - K * M
无论怎样排列，sum(A) + sum(B) 都是固定的。因此：
最小化
S，等价于最大化满足A[i] + B[p[i]] >= M的配对数量。
问题由“最小化取模和”转化成了一个最大匹配数量问题。
贪心策略
将 A、B 都从小到大排序，并保留每个元素的原下标。
使用两个指针：
left指向当前最小的Aright指向当前最大的B
每次判断 A[left] + B[right]：
情况一：两数之和大于等于 M
将它们配对，可以产生一次进位。随后同时移动两个指针：
left++
right--
情况二：两数之和小于 M
当前 A[left] 与最大的 B[right] 相加都无法达到 M，那么它与任何剩余的 B 配对都无法产生进位。
因此，可以将当前 A[left] 标记为未匹配，并执行：
left++
最后，把未产生进位的 A 与剩余的 B 任意配对即可。
为什么贪心是正确的
如果当前最小的 A 加上最大的 B 仍小于 M，那么这个 A 不可能与任何剩余元素形成有效配对，跳过它不会损失答案。
如果两数之和大于等于 M，则可以让当前最小的 A 与最大的 B 配对。剩余的 A 都不小于当前元素，它们只会更容易满足配对条件，因此该选择不会减少后续可形成的有效配对数量。
不断执行上述选择，就能得到最大的进位次数 K，从而得到最小的 S。
Node.js 实现
假设输入格式如下：
N M
A1 A2 ... AN
B1 B2 ... BN
代码同时输出最小值和一个满足条件的排列。排列下标从 1 开始：
const fs = require('fs')
const tokens = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number)
let pos = 0
const n = tokens[pos++]
const m = tokens[pos++]
const a = tokens.slice(pos, pos + n)
pos += n
const b = tokens.slice(pos, pos + n)
const sortedA = a
.map((value, index) => ({ value, index }))
.sort((x, y) => x.value - y.value)
const sortedB = b
.map((value, index) => ({ value, index }))
.sort((x, y) => x.value - y.value)
const permutation = Array(n)
const unmatchedA = []
let left = 0
let right = n - 1
let carryCount = 0
while (left < n && right >= 0) {
if (sortedA[left].value + sortedB[right].value >= m) {
permutation[sortedA[left].index] = sortedB[right].index + 1
carryCount++
left++
right--
} else {
unmatchedA.push(sortedA[left].index)
left++
}
}
while (left < n) {
unmatchedA.push(sortedA[left].index)
left++
}
// 未使用的 B 恰好是 sortedB[0...right]。
for (let i = 0; i < unmatchedA.length; i++) {
permutation[unmatchedA[i]] = sortedB[i].index + 1
}
// 使用 BigInt，避免总和超过 Number 的安全整数范围。
const total = [...a, ...b].reduce((sum, value) => sum + BigInt(value), 0n)
const minSum = total - BigInt(carryCount) * BigInt(m)
console.log(minSum.toString())
console.log(permutation.join(' '))
如果题目只要求输出最小值，不要求给出具体排列，可以删除 permutation 相关代码，仅统计 carryCount。
复杂度分析
- 排序时间复杂度：
O(N log N) - 双指针扫描时间复杂度：
O(N) - 总时间复杂度：
O(N log N) - 空间复杂度：
O(N)
总结
这道题的关键是观察到：每出现一次 A[i] + B[p[i]] >= M，最终答案就会减少一个 M。因此不需要直接优化每一项的余数，只需要通过排序和双指针，让进位配对的数量尽可能多。