首页 > 试题广场 >

小红的整数配对

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

热度指数：2836 时间限制：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

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)

赵金布

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

list1=sorted(list(map(int,input().split())),reverse=True)

score=0

l=len(list1)

i=0

while i<=l-2:#从大到小遍历元素

if abs(list1[i]-list1[i+1])<=k:

score+=list1[i]*list1[i+1]

i+=2#匹配到标记下标

else:

i+=1#未匹配到标记下标

print(score)

发表于 2025-11-18 18:24:38 回复(0)

牛客341639822号

''' 用切片赋值的方法来更新列表，运行超时，使用pop方法在原列表上进行删除，就通过了 ''' n, k = map(int, input().split())
st = [int(x) for x in input().split()]
st.sort()
result = 0 i = n-1 while len(st) > 1: if st[i] - st[i-1] <= k:
        result += st[i] * st[i-1]
        st.pop()
        st.pop()
        i -= 2  else:
        st.pop()
        i -= 1 print(result)

发表于 2025-10-04 14:22:58 回复(0)

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)

草海桐

/* 
    先排序，从最大的一边开始遍历
 */
package main

import (
	"fmt"
	"sort"
)

func main() {
    var n,k, result int
    fmt.Scanf("%d %d", &n, &k)
    var a = make([]int, n)
    for i:=0;i<n;i++{
        fmt.Scanf("%d", &a[i])
    }
    sort.Ints(a)
    for i:=len(a)-1;i>=1;{
        if a[i] - a[i-1] <= k {
            result+= a[i]*a[i-1]
            i -=2
        }else{
            i--
        }
    }
    fmt.Println(result)
}

发表于 2025-09-07 13:57:08 回复(0)

Python3

牛客847294653号

from collections import deque

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

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

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

a = deque(a) # 转换为deque以使用popleft()

score = 0

while len(a) > 1: # 至少需要两个元素才能配对

if abs(a[0] - a[1]) <= k: # 检查第一和第二大的数是否可以配对

score += a[0] * a[1]

a.popleft() # 移除第一个元素

a.popleft() # 移除第二个元素（原来的第二个，现在是第一个）

else:

a.popleft() # 如果不能配对，移除较大的数

print(score)

发表于 2025-08-25 19:06:27 回复(0)

牛客113445882号

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

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

sum = 0

a.sort(reverse = True)

x = 0

while x < n - 1:

if a[x] - a[x+1] <= k:

sum += a[x] * a[x+1]

x += 2

else:

x +=1

print(sum)

发表于 2025-06-21 20:45:24 回复(0)

提交观点

问题信息

贪心

难度：

7条回答 20收藏 184浏览

小红的整数配对

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题