小红的整数配对

[题目链接](https://www.nowcoder.com/practice/7fc314de9064479baddd77848c4c7d95)

思路

本题要求从数组中选若干对数进行配对，每对数的差值不超过 $k$ ，使得所有配对数的乘积之和最大。

排序 + 贪心观察

首先将数组排序。排序后，如果要配对两个数，它们在排序后的数组中一定是相邻的才最优。为什么？

假设排序后有四个数 $a \leq b \leq c \leq d$ ，如果 $a, d$ 和 $b, c$ 都能配对（差值不超过 $k$ ），那么 $ad + bc$ 与 $ab + cd$ 哪个更大？

$ $ab + cd - (ad + bc) = a(b-d) + c(d-b) = (c-a)(d-b) \geq 0$ $

所以 $ab + cd \geq ad + bc$ ，即相邻配对总是不劣于交叉配对。

动态规划

排序后，问题变成：在有序数组上，每次只能选相邻的两个元素配对（前提是差值 $\leq k$ ），求最大乘积之和。

定义 $dp[i]$ 为考虑前 $i$ 个元素时能获得的最大分数：

不配对第 $i$ 个元素： $dp[i] = dp[i-1]$
将第 $i$ 个与第 $i-1$ 个配对（仅当 $a[i] - a[i-1] \leq k$ ）： $dp[i] = dp[i-2] + a[i] \times a[i-1]$

取两者的较大值即可。

举例

数组 $[1, 1, 4, 5, 1, 4]$ ， $k = 2$ 。

排序后： $[1, 1, 1, 4, 4, 5]$ 。

$i$	元素	差值	不配对	配对	$dp[i]$
1	1	—	0	—	0
2	1	0	0	$0 + 1 \times 1 = 1$	1
3	1	0	1	$0 + 1 \times 1 = 1$	1
4	4	3 > 2	1	不可配	1
5	4	0	1	$1 + 4 \times 4 = 17$	17
6	5	1	17	$1 + 5 \times 4 = 21$	21

答案为 $21$ ，对应配对 $(4, 5)$ 和 $(1, 1)$ 。

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    vector<long long> a(n);
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    sort(a.begin(), a.end());
    // dp[i] = max score using first i elements (1-indexed)
    vector<long long> dp(n + 1, 0);
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i - 1]; // skip a[i-1]
        if(i >= 2 && a[i-1] - a[i-2] <= k){
            dp[i] = max(dp[i], dp[i - 2] + a[i-1] * a[i-2]);
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

[sol-Java]

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        long[] a = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
        Arrays.sort(a);
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            if (i >= 2 && a[i - 1] - a[i - 2] <= k) {
                dp[i] = Math.max(dp[i], dp[i - 2] + a[i - 1] * a[i - 2]);
            }
        }
        System.out.println(dp[n]);
    }
}

[sol-Python3]

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]
        if i >= 2 and a[i - 1] - a[i - 2] <= k:
            dp[i] = max(dp[i], dp[i - 2] + a[i - 1] * a[i - 2])
    print(dp[n])

main()

[sol-JavaScript]

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, k] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    a.sort((x, y) => x - y);
    const dp = new Array(n + 1).fill(BigInt(0));
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        if (i >= 2 && a[i - 1] - a[i - 2] <= k) {
            const prod = BigInt(a[i - 1]) * BigInt(a[i - 2]);
            const candidate = dp[i - 2] + prod;
            if (candidate > dp[i]) dp[i] = candidate;
        }
    }
    console.log(dp[n].toString());
});

复杂度分析

时间复杂度： $O(n \log n)$ ，排序 $O(n \log n)$ ，DP 遍历 $O(n)$ 。
空间复杂度： $O(n)$ ，用于存储数组和 DP 数组。