题目链接

小红的整数配对

题目描述

小红有一个长度为 的数组。小红初始分数为 。小红每次选择两个整数，这两个数的差值不能超过 ，小红获得这两个数的乘积的分数，被选择过的数不能再选择。问小红最多能获得多少分数？

输入:

  • 第一行输入两个整数 和
  • 第二行输入 个整数

输出:

  • 输出一个整数，表示小红能获得的最大分数

解题思路

这是一个贪心问题，可以通过以下步骤解决：

  1. 关键发现：

    • 两个数的差值不能超过
    • 每个数只能使用一次
    • 需要使乘积和最大

  2. 解题策略：

    • 将数组排序
    • 从大到小遍历数组
    • 对每个数找到差值不超过 的最大数配对
    • 使用标记数组避免重复使用

  3. 具体步骤：

    • 对数组进行排序
    • 从大到小遍历每个数
    • 在未使用的数中找到差值不超过 的最大数
    • 累加乘积到答案中

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 排序
    sort(a.begin(), a.end());
    
    vector<bool> used(n, false);
    long 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 long)a[i] * a[maxj];
            used[i] = used[maxj] = true;
        }
    }
    
    cout << ans << endl;
    return 0;
}

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

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

# 排序
a.sort()

used = [False] * n
ans = 0

# 从大到小遍历
for i in range(n-1, -1, -1):
    if used[i]:
        continue
    
    # 找到差值不超过k的最大未使用数
    maxj = -1
    for j in range(i-1, -1, -1):
        if not used[j] and a[i] - a[j] <= k:
            maxj = j
            break
    
    if maxj != -1:
        ans += a[i] * a[maxj]
        used[i] = used[maxj] = True

print(ans)

算法及复杂度

  • 算法：贪心
  • 时间复杂度： - 排序的复杂度
  • 空间复杂度： - 需要存储标记数组

注意：

  1. 需要使用 long long/long 类型避免乘法溢出
  2. 从大到小遍历可以保证获得最大乘积
  3. 使用标记数组避免重复使用数字
  4. 注意差值不超过 的判断条件