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

题目链接

小红的整数配对

题目描述

小红有一个长度为 $n$ 的整数数组 $a$ 。她可以执行多次操作来将数组中的数两两配对。

配对规则：选择两个尚未被选过的数 $a_i$ 和 $a_j$ ，如果它们满足 $|a_i - a_j| \le k$ ，则可以配对。
得分规则：每成功配对一对，她就可以获得 $a_i \cdot a_j$ 的分数。
配对后的数将被移除，不能再次使用。

目标是帮助小红找到一种配对方案，使得最终的总得分最大。

解题思路

这是一个寻求最优配对以最大化总分的组合优化问题。由于得分与配对的数值大小正相关（数值越大，乘积越大），我们可以采用贪心策略来解决。

核心思想：优先配对最大的数

为了让总分最大，我们应该尽可能地让大的数与大的数相乘。这引导我们从大到小处理数组中的数。

排序：首先，我们将数组 $a$ 按升序排序。排序后，数值相近的数会聚集在一起，这便于我们判断配对条件 $|a_i - a_j| \le k$ 。对于已排序的数组，该条件等价于 $a_j - a_i \le k$ （假设 $a_j \ge a_i$ ）。
从大到小贪心匹配：我们从数组的末尾（即最大的数）开始向前遍历。
- 考虑当前可用的最大数 a[i]。为了最大化得分 a[i] * partner，我们应该为它寻找一个满足条件的、尽可能大的伙伴。
- 在排好序的数组中，a[i] 可用的、最大的伙伴就是它左边相邻的数 a[i-1]。
- 于是，我们的贪心策略变得非常清晰：
  - 检查：判断 a[i] 和 a[i-1] 能否配对，即 a[i] - a[i-1] <= k 是否成立。
  - 如果能配对：这一定是 a[i] 能产生的最优配对（因为 a[i-1] 是它能匹配的最大伙伴）。我们确认这对配对，将它们的乘积 a[i] * a[i-1] 加入总分，然后同时“移除”这两个数，继续从 i-2 开始考察。
  - 如果不能配对：由于 a[i-1] 是 a[i] 能找到的最大伙伴，如果连它都不行，那么更小的数（如 a[i-2] 等）更不可能满足条件（因为差值会更大）。因此，a[i] 在这种情况下无法与任何数配对，我们只能将它“丢弃”，然后从 i-1 开始考察。
实现：这个过程可以通过一个从 n-1 开始递减的指针 i 来实现。根据配对是否成功，i 每次递减 2 或 1。

算法步骤

读入 n, k 和数组 a。
对数组 a 进行升序排序。
初始化总分 score = 0。
使用一个指针 i 从 n-1 开始循环，直到 i <= 0。
在循环中，检查 a[i] - a[i-1] <= k。
- 若为真，score += a[i] * a[i-1]，并且 i -= 2。
- 若为假，i -= 1。
循环结束后，score 即为最大得分。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

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());

    long long score = 0;
    for (int i = n - 1; i > 0; ) {
        if (a[i] - a[i - 1] <= k) {
            score += a[i] * a[i - 1];
            i -= 2;
        } else {
            i -= 1;
        }
    }

    cout << score << endl;

    return 0;
}

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

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 score = 0;
        for (int i = n - 1; i > 0; ) {
            if (a[i] - a[i - 1] <= k) {
                score += a[i] * a[i - 1];
                i -= 2;
            } else {
                i -= 1;
            }
        }

        System.out.println(score);
    }
}

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    a.sort()
    
    score = 0
    i = n - 1
    while i > 0:
        if a[i] - a[i-1] <= k:
            score += a[i] * a[i-1]
            i -= 2
        else:
            i -= 1
            
    print(score)

solve()

算法及复杂度

算法：贪心
时间复杂度：算法的主要开销在于排序，时间复杂度为 $\mathcal{O}(N \log N)$ 。排序后的贪心匹配过程是一个单次遍历，复杂度为 $\mathcal{O}(N)$ 。因此，总时间复杂度为 $\mathcal{O}(N \log N)$ 。
空间复杂度：主要为存储数组所需空间，以及排序可能产生的额外空间。通常认为是 $\mathcal{O}(N)$ 。