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

题目链接

小红的整数配对

题目描述

小红有一个包含 $n$ 个整数的数组 $a$ 。她可以进行多次配对操作来获得分数。操作规则如下：

选择两个尚未被选过的数 $a_i$ 和 $a_j$ 。
如果它们的绝对值之差不大于 $k$ ，即 $|a_i - a_j| \le k$ ，则配对成功。
配对成功后，获得 $a_i \cdot a_j$ 的分数，并且这两个数被移除，不能再次使用。
目标是最大化总得分。

解题思路

这是一个组合优化问题。为了最大化总得分（乘积之和），我们应该优先让数值大的数互相配对，因为这比让大数和小数配对的得分贡献要大得多。这引导我们采用贪心策略。

核心贪心策略：大数优先配对

排序：首先，我们将整个数组 a 从大到小进行排序。这使得我们总能优先处理当前最大的可用数字。
配对：我们从左到右遍历排序后的数组。
- 当我们遇到第一个尚未被配对的数 a[i] 时，它就是当前所有剩余数字中最大的。为了最大化得分，我们应该为它寻找一个尽可能大的、符合条件的搭档。
- 我们继续向右寻找第一个同样尚未被配对的数 a[j]。
- 检查这两个数 a[i] 和 a[j] 是否满足配对条件：a[i] - a[j] <= k。（因为数组是降序的，所以 a[i] >= a[j]，可以直接去掉绝对值符号）。
- 如果满足条件：
  - 这意味着 a[j] 是 a[i] 能找到的、最大的、可行的搭档。我们将它们配对，把得分 a[i] * a[j] 累加到总分中。
  - 然后将 a[i] 和 a[j] 都标记为“已使用”。
- 如果不满足条件：
  - 这意味着 a[j] 以及它右边的所有数（因为它们更小，差值会更大）都无法与 a[i] 配对。
  - 因此，a[i] 无法找到任何搭档，我们只能放弃它。
迭代：我们重复上述过程，不断地为当前最大的可用数寻找搭档，直到遍历完整个数组。

算法步骤

读取输入 n, k 和数组 a。
将数组 a 降序排序。
初始化总分 total_score = 0。
使用一个布尔数组 used 来标记每个数字是否已被配对，初始值都为 false。
使用一个指针 i 从 0 遍历到 n-1：
- 如果 used[i] 为 true，跳过。
- a[i] 是当前最大的可用数。我们再用一个指针 j 从 i+1 开始向右寻找搭档。
- 找到第一个 used[j] 为 false 的数 a[j]。
- 如果 a[i] - a[j] <= k，则配对成功：
  - total_score += a[i] * a[j]
  - used[i] = true
  - used[j] = true
遍历结束后，total_score 就是最大总得分。

代码

c++
java
python

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

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.rbegin(), a.rend()); // 降序排序

    vector<bool> used(n, false);
    long long total_score = 0;

    int j = 0;
    for (int i = 0; i < n; ++i) {
        if (used[i]) {
            continue;
        }
        
        // 为 a[i] 寻找搭档
        j = i + 1;
        while(j < n && used[j]) {
            j++;
        }

        if (j < n) { // 找到了一个未使用的 a[j]
            if (a[i] - a[j] <= k) {
                total_score += a[i] * a[j];
                used[i] = true;
                used[j] = true;
            }
        }
    }

    cout << total_score << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();

        List<Long> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            a.add(sc.nextLong());
        }

        a.sort(Collections.reverseOrder()); // 降序排序

        boolean[] used = new boolean[n];
        long totalScore = 0;

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }

            int j = i + 1;
            while(j < n && used[j]) {
                j++;
            }

            if (j < n) { // 找到了一个未使用的 a[j]
                if (a.get(i) - a.get(j) <= k) {
                    totalScore += a.get(i) * a.get(j);
                    used[i] = true;
                    used[j] = true;
                }
            }
        }
        System.out.println(totalScore);
    }
}

import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    a.sort(reverse=True) # 降序排序

    used = [False] * n
    total_score = 0
    
    j = 0
    for i in range(n):
        if used[i]:
            continue

        j = i + 1
        while j < n and used[j]:
            j += 1
        
        if j < n: # 找到了一个未使用的 a[j]
            if a[i] - a[j] <= k:
                total_score += a[i] * a[j]
                used[i] = True
                used[j] = True

    print(total_score)

solve()

算法及复杂度

算法：贪心
时间复杂度：
- 对数组进行排序需要 $\mathcal{O}(n \log n)$ 。
- 排序后，我们用两个指针 i 和 j 遍历数组。虽然内层有 while 循环，但每个元素最多被 j 访问一次。因此，遍历和配对过程的总时间复杂度为 $\mathcal{O}(n)$ 。
- 整体时间复杂度的瓶颈在于排序，为 $\mathcal{O}(n \log n)$ 。
空间复杂度：我们需要一个布尔数组来记录每个元素的使用状态，因此空间复杂度为 $\mathcal{O}(n)$ 。