HJ175 小红的整数配对

• 题目
• 题解(31)
• 讨论(12)
• 排行

简单 通过率：41.60% 时间限制：1秒 空间限制：256M

知识点贪心

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

小红拥有一个长度为 nn 的整数数组 {a1,a2,…,an}{a1​,a2​,…,an​}，初始得分为 00。
她可以多次执行如下操作，顺序不限、次数不限，直到无法继续：
∙ ∙ 任选两个尚未被选过的下标 i≠ji​=j；
∙ ∙ 若满足 ∣ai−aj∣≦k∣ai​−aj​∣≦k，则将这两个数配成一对，并获得分数 ai×ajai​×aj​；否则该对无法选取；
∙ ∙ 被配对的两个数随即从数组中移除，之后不可再次使用。

请你帮助小红最大化最终得分，并输出这个最大分数。

输入描述：

在一行上输入两个整数 n,k(1≦n,k≦105)n,k(1≦n,k≦105)。
在第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦105)a1​,a2​,…,an​(1≦ai​≦105)。

输出描述：

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

示例1

输入：

6 2 1 1 4 5 1 4

复制输出：

21

复制说明：

一种可行的最优方案如下： ∙ ∙ 选择 11 与 11，得分 1×1=11×1=1； ∙ ∙ 选择 44 与 55，得分 4×5=204×5=20； 最终总得分为 1+20=211+20=21。

#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; long long k; cin >> n >> k; vector<long long> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); long long score = 0; for (int i = n - 1; i > 0; ) { if (a[i] - a[i - 1] <= k) { score += a[i] * a[i - 1]; i -= 2; } else { i -= 1; } } cout << score << endl; return 0; }