首页 > 试题广场 >

小红的整数配对

[编程题]小红的整数配对

热度指数：2845 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红拥有一个长度为 $n$ 的整数数组 $\{a_1,a_2,\dots,a_n\}$ ，初始得分为 $0$ 。
$\hspace{15pt}$ 她可以多次执行如下操作，顺序不限、次数不限，直到无法继续：
$\hspace{23pt}\bullet\,$ 任选两个尚未被选过的下标 $i\neq j$ ；
$\hspace{23pt}\bullet\,$ 若满足 $|a_i-a_j|\leqq k$ ，则将这两个数配成一对，并获得分数 $a_i\times a_j$ ；否则该对无法选取；
$\hspace{23pt}\bullet\,$ 被配对的两个数随即从数组中移除，之后不可再次使用。

$\hspace{15pt}$ 请你帮助小红最大化最终得分，并输出这个最大分数。

输入描述:

在一行上输入两个整数 。
在第二行输入  个整数 。

输出描述:

输出一个整数，表示通过最优配对操作后小红能够获得的最大得分。

示例1

输入

6 2
1 1 4 5 1 4

输出

说明

一种可行的最优方案如下：
 选择  与 ，得分 ；
 选择  与 ，得分 ；
最终总得分为 。

算法知识视频讲解

Java

牛客916838684号

和上面那位老哥思路一样

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] num = new int[n];

        int count =0;

        for(int i=0; i<n; i++){
            num[i] = in.nextInt();
        }

        Arrays.sort(num);

        for(int i= num.length-1; i>0; i=i-1){
            if(num[i]- num[i-1] <=k){
                count = count +  num[i] * num[i-1];
                num[i]=0;
                num[i-1] =0;
                // System.out.println("执行了乘法");
                i = i-1;
            }

        }

        System.out.println(count);
    }
}

发表于 2025-09-29 10:25:45 回复(0)

Java

BraveCoder

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] an = new int[n];
        for(int i=0;i<n;i++){
            an[i] = in.nextInt();
        }

        Arrays.sort(an); // 从小到大排序，后续从后往前取最大元素
        long sum = 0; // 改为long，防止数据溢出
        
        // 从后往前遍历，优先配对最大和次大元素
        for(int i = n-1; i > 0; i--){
            // 满足条件则配对，累加乘积
            if(an[i] - an[i-1] <= k){
                sum += (long)an[i] * an[i-1]; // 强制转型，避免int相乘溢出
                i--; // 跳过已配对的次大元素
            }
        }
        System.out.println(sum);
    }
}

发表于 2025-09-04 20:49:40 回复(0)

提交观点

问题信息

贪心

难度：

3条回答 20收藏 190浏览

小红的整数配对

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题