首页 > 试题广场 >

小红的整数配对

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

热度指数：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

输出

说明

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

算法知识视频讲解

草海桐

/* 
    先排序，从最大的一边开始遍历
 */
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)