题解 | #小红的整数配对#

题目链接

小红的整数配对

题目描述

小红有一个长度为 $n$ 的数组 $a$ 。她可以多次执行如下操作：

选择数组中两个之前未被选择过的整数 $a_i$ 和 $a_j$ ，需满足 $|a_i - a_j| \le k$ 。
获得 $a_i \cdot a_j$ 的分数。

问小红最多能获得多少分数？

解题思路

这是一个可以通过动态规划解决的最优配对问题。

1. 预处理

为了最大化乘积之和，我们应该优先考虑将数值相近且较大的数配对。这启发我们首先对数组进行排序。将数组 $a$ 从小到大排序后，配对条件 $|a_i - a_j| \le k$ (假设 $i < j$ ) 就简化为 $a_j - a_i \le k$ 。

2. 动态规划

排序后，问题具有了最优子结构，适合使用动态规划求解。

状态定义：

我们定义 $dp[i]$ 为：考虑排序后数组的前 $i$ 个元素（即 $a_0, \dots, a_{i-1}$ ）所能获得的最大分数。
状态转移方程：

在计算 $dp[i]$ 时，我们主要关注第 $i$ 个元素 $a_{i-1}$ 的决策。它有两种可能：
1. $a_{i-1}$ 不参与配对：如果 $a_{i-1}$ 不与任何元素配对，那么它就被放弃了。此时，前 $i$ 个元素能获得的最大分数就等于只考虑前 $i-1$ 个元素时的最大分数。即 $dp[i] = dp[i-1]$ 。
2. $a_{i-1}$ 与 $a_{i-2}$ 配对：如果我们将 $a_{i-1}$ 与它紧邻的前一个元素 $a_{i-2}$ 配对，这必须满足条件 $a_{i-1} - a_{i-2} \le k$ 。如果满足，我们会获得 $a_{i-1} \cdot a_{i-2}$ 的分数，并且这两个元素都不能再被使用。此时的总分数为这对元素的分数加上前 $i-2$ 个元素能获得的最大分数，即 $dp[i-2] + (long long)a_{i-1} \cdot a_{i-2}$ 。
综合这两种情况， $dp[i]$ 的值应为两者的最大值。因此，转移方程为：
- $dp[i] = dp[i-1]$
- 如果 $i \ge 2$ 且 $a_{i-1} - a_{i-2} \le k$ ，则 $dp[i] = \max(dp[i], dp[i-2] + (long long)a_{i-1} \cdot a_{i-2})$
基础情况：
- $dp[0] = 0$ (没有元素，分数为0)
- $dp[1] = 0$ (只有一个元素，无法配对，分数为0)
最终答案：

最终结果为 $dp[n]$ 。

注意：分数可能会很大，需要使用 64 位整型（long long）来存储。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    vector<long long> dp(n + 1, 0);

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1]; // Case 1: a[i-1] is not paired
        if (a[i-1] - a[i-2] <= k) {
            dp[i] = max(dp[i], (i > 2 ? dp[i-2] : 0) + a[i-1] * a[i-2]);
        }
    }

    cout << dp[n] << endl;

    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Arrays.sort(a);

        long[] dp = new long[n + 1];

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1]; // Case 1: a[i-1] is not paired
            if (a[i - 1] - a[i - 2] <= k) {
                long pairScore = a[i - 1] * a[i - 2];
                long previousScore = (i > 2) ? dp[i - 2] : 0;
                dp[i] = Math.max(dp[i], previousScore + pairScore);
            }
        }

        System.out.println(dp[n]);
    }
}

import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    a.sort()
    
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] # Case 1: a[i-1] is not paired
        if a[i-1] - a[i-2] <= k:
            pair_score = a[i-1] * a[i-2]
            previous_score = dp[i-2] if i > 2 else 0
            dp[i] = max(dp[i], previous_score + pair_score)
            
    print(dp[n])

solve()

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(n \log n)$ ，瓶颈在于对数组的排序。DP 过程本身是线性的，为 $\mathcal{O}(n)$ 。
空间复杂度： $\mathcal{O}(n)$ ，用于存储 DP 状态数组。