首页 > 试题广场 >

小红的整数配对

[编程题]小红的整数配对
  • 热度指数：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}请你帮助小红最大化最终得分，并输出这个最大分数。

输入描述:
\hspace{15pt}在一行上输入两个整数 n,k\left(1\leqq n,k\leqq 10^5\right)。
\hspace{15pt}在第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\leqq a_i\leqq 10^5\right)。


输出描述:
\hspace{15pt}输出一个整数，表示通过最优配对操作后小红能够获得的最大得分。
示例1

输入

6 2
1 1 4 5 1 4

输出

21

说明

\hspace{15pt}一种可行的最优方案如下：
\hspace{23pt}\bullet\, 选择 1 与 1，得分 1\times1=1；
\hspace{23pt}\bullet\, 选择 4 与 5，得分 4\times5=20；
\hspace{15pt}最终总得分为 1+20=21。
算法知识视频讲解
添加回答
Python3
牛客847294653号头像 牛客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)
提交观点

问题信息

贪心
难度：
1条回答 191浏览

热门推荐

相关试题

小红的整数配对

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号