题解 | 小红的整数配对

1. 关键发现：两个数的差值不能超过 每个数只能使用一次需要使乘积和最大
2. 解题策略：将数组排序从大到小遍历数组对每个数找到差值不超过  的最大数配对使用标记数组避免重复使用
3. 具体步骤：对数组进行排序从大到小遍历每个数在未使用的数中找到差值不超过  的最大数累加乘积到答案中

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        // 排序
        Arrays.sort(a);
        
        boolean[] used = new boolean[n];
        long ans = 0;
        
        // 从大到小遍历
        for(int i = n-1; i >= 0; i--) {
            if(used[i]) continue;
            
            // 找到差值不超过k的最大未使用数
            int maxj = -1;
            for(int j = i-1; j >= 0; j--) {
                if(!used[j] && a[i] - a[j] <= k) {
                    maxj = j;
                    break;
                }
            }
            
            if(maxj != -1) {
                ans += (long)a[i] * a[maxj];
                used[i] = used[maxj] = true;
            }
        }
        
        System.out.println(ans);
    }
}