首页 > 试题广场 >

小红的整数配对

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

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

输出

说明

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

算法知识视频讲解

计算机252班卢梦

#include <stdio.h>
#include <stdlib.h>

// 排序比较函数
int cmp(const void *a, const void *b) {
return (*(long long*)a - *(long long*)b);
}

int main() {
int n, k;
scanf("%d%d", &n, &k);
long long a[100005], dp[100005] = {0}; // 直接定义数组，dp初始化为0

// 读入数组
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
// 升序排序
qsort(a, n, sizeof(long long), cmp);

// 动态规划核心
for (int i = 1; i <= n; i++) {
dp[i] = dp[i-1]; // 不选第i个数
// 满足配对条件则更新
if (i >= 2 && a[i-1] - a[i-2] <= k) {
dp[i] = dp[i] > (dp[i-2] + a[i-1]*a[i-2]) ? dp[i] : (dp[i-2] + a[i-1]*a[i-2]);
}
}

printf("%lld\n", dp[n]);
return 0;
}

发表于 2026-01-30 19:59:51 回复(0)