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×111×11 ∙ ∙ 选择 44 与 55得分 4×5204×520 最终总得分为 1202112021。#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; vectorlong 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; }