题解 | 小红的整数配对

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  贪心：1. 相乘的数尽可能接近； 2. 优先为大的数匹配； 3. 作者不会数学证明。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define all(x) x.begin(), x.end()
#define ll long long

int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  sort(all(a));//---排序
  int index = n - 2;//--------记录选取的数中小的哪个数的索引
  ll ans = 0;
  while(index >= 0){
    if (a[index + 1] - a[index] <= k){
      ans += static_cast<ll>(a[index + 1]) * a[index];//---------10^5,用ll放溢出
      index -= 2;
    }
    else{
      index--;
    }
  }
  cout << ans;
  return 0;
}
// 64 位输出请用 printf("%lld")