BISHI48　小红的整数配对¶

简单通过率 42.46%python3样例通过牛客 AC贪心

牛客原题　源码

讲解章节：贪心

一句话

把数两两配对（差不超过 k），最大化 Σ a_i*a_j。

解题思路¶

这题考什么¶

排序 + 从大到小的相邻贪心：

把数组升序排序；
从最大的开始往前扫，若 a[i] 与 a[i-1] 的差 <= k 就把它俩配对（得分 a[i]*a[i-1]），指针跳 2 格；否则 a[i] 只能被丢弃，指针跳 1 格。

为什么对：

若 a[n-1] - a[n-2] > k，那么 a[n-1] 与任何更小的数差距只会更大，它必然配不出去，直接丢弃；
否则设最优解里 a[n-1] 配 x、a[n-2] 配 y（x, y 是更小的元素），交换成 (a[n-1], a[n-2]) 与 (x, y)，收益变化为 a[n-1]a[n-2] + xy - a[n-1]x - a[n-2]y = (a[n-1]-y)(a[n-2]-x) >= 0，不会变差；而且 x >= a[n-1]-k >= a[n-2]-k、y >= a[n-2]-k，又都 <= a[n-2]，所以 x 和 y 同处一个长度为 k 的区间内，|x-y| <= k，新配对合法。若最优解里只有 a[n-2] 配了 y 而 a[n-1] 闲置，换成 a[n-1] 配 a[n-2] 同样不亏（a[n-1]a[n-2] >= a[n-2]y）。
逐步归纳即得贪心最优。

验算样例：[1,1,1,4,4,5]，k=2。5 与 4 差 1 -> 配对 20；剩 [1,1,1,4]，4 与 1 差 3 > 2 -> 丢掉 4；剩 [1,1,1]， 1 与 1 配对得 1；总分 21 ✓。

数据规模与复杂度¶

n,k <= 1e5，a_i <= 1e5。排序 O(n log n) + 扫描 O(n)。得分上界约 (n/2)*1e10 = 5e14，C/C++ 必须 long long。

坑在哪¶

一定要从大端开始配，从小端开始会把大数配错（比如 [1,4,5], k=2：从小端会先配 1-4? 差 3 不合法，再配 4-5 得 20 恰好也对，但 [3,4,5], k=1 从小端配 3-4 得 12，从大端配 4-5 得 20，差别就出来了）；
「未被选过的下标」意味着每个数最多配一次，不能重复使用；
允许不配对（不是必须全配），配不上就直接跳过；
循环条件是 i > 0 而不是 i >= 0：i == 0 时左边已经没有搭档，写成 i >= 0 会访问 a[-1]（Python 里是末尾元素），得出离谱的配对。

贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI48.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = sorted(int(v) for v in data[2:2 + n])   # 升序后「差 <= k」只需看相邻两项
    ans = 0
    i = n - 1                          # 从最大的一端往回扫；i == 0 时左边无人可配
    while i > 0:
        if a[i] - a[i - 1] <= k:      # 最大的两个能配就配，收益最优
            ans += a[i] * a[i - 1]
            i -= 2
        else:                          # 配不上任何人，只能丢弃
            i -= 1
    print(ans)


main()

BISHI48 小红的整数配对¶