小红的整数配对

思路

题意：给 n 个整数和一个阈值 m，每次可以选两个还没被选过的数配对，条件是两数之差的绝对值不超过 m，配对得分为两数之积。问最大总得分是多少。

贪心策略很直觉——大数配大数，收益最高。具体怎么做？

  1. 排序。排完序后，能配对的数一定是"挨得近"的，因为差值不超过 m。
  2. 从右往左贪心配对。从最大的数开始看，如果它和前一个数的差 <= m，就把它俩配上（乘积最大化），然后跳过这两个继续往左看；如果差值 > m，说明当前这个数找不到合法的配对伙伴（左边的只会更小，差值只会更大），只能放弃它，往左移一位。

为什么从右往左贪心是对的？排序后，最大的数如果能配对，它和相邻的数配是最优的（相邻的数是所有合法候选中最大的，乘积最大）。如果不能配对就只能浪费掉。这个贪心选择不会影响后续的最优性，因为跳过一个无法配对的大数不会让后面的配对变差。

拿示例验证：数组 [1,1,4,5,1,4]，m=2。排序后 [1,1,1,4,4,5]。从右往左：5 和 4 差值 1<=2，配对得 20；下一对 4 和 1 差值 3>2，跳过 4；1 和 1 差值 0<=2，配对得 1。总分 21，正确。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    long long ans = 0;
    int i = n - 1;
    while (i >= 1) {
        if (a[i] - a[i-1] <= m) {
            ans += a[i] * a[i-1];
            i -= 2;                 // 配对成功，跳两步
        } else {
            i -= 1;                 // 当前数没法配，跳过
        }
    }
    cout << ans << 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();
        int m = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        Arrays.sort(a);

        long ans = 0;
        int i = n - 1;
        while (i >= 1) {
            if (a[i] - a[i - 1] <= m) {
                ans += a[i] * a[i - 1];
                i -= 2;
            } else {
                i -= 1;
            }
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

ans = 0
i = n - 1
while i >= 1:
    if a[i] - a[i-1] <= m:
        ans += a[i] * a[i-1]
        i -= 2
    else:
        i -= 1

print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const a = lines[1].split(' ').map(Number);
    a.sort((x, y) => x - y);

    let ans = 0;
    let i = n - 1;
    while (i >= 1) {
        if (a[i] - a[i - 1] <= m) {
            ans += a[i] * a[i - 1];
            i -= 2;
        } else {
            i -= 1;
        }
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度: ，瓶颈在排序，贪心扫描是 。
  • 空间复杂度: ，存数组。

小结

排序 + 从右往左贪心，核心就一个循环。大的数优先配对，能配就配，不能配就扔掉。因为大数和大数配乘积最大，而且排序后相邻的数差值最小、最容易满足 <= m 的条件，所以贪心策略天然就是最优的。