题解 | #小红的最大价值#

上AC代码

11行！！！

 #include <bits/stdc++.h>
using namespace std;
int main()
 {
  int n , k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i = 0 ; i <= n - 1 ; ++ i) cin >> a[i];
  sort(a.begin() , a.end());
  cout << (abs(a[0] - a[n - 1])> k ? a[n - 1] : a[n - 2]);
}

题目：

小红有一个长度为 𝑛n 的数组，定义一个数对的 𝑎[i],a[j](i < j)的价值为：如果 ∣𝑎𝑖−𝑎𝑗∣>𝑘，则价值为 max(𝑎𝑖,𝑎𝑗)，否则价值为 min(𝑎𝑖,𝑎𝑗)。小红想知道所有数对的最大价值是多少。

思路：

题目中表示一个数对a[i] , a[j] （i< j） , 在后面 ∣𝑎𝑖−𝑎𝑗∣>𝑘中，减法加了绝对值.注意：i，j 可以随便取，只要满足i < j

**max(𝑎𝑖,𝑎𝑗)**的意思就是找到大于 k 的最大差值 ， 即最小值减最大值，题目中没表达需要排序，但是无论小值在前面还是大值在前面，数组的最小值和最大值还是能够相减取绝对值.

如果最小值减最大值 > k，则所有数对的最大价值一定是数组的最大元素

反之，因为|a[0] - a[n - 1]|是最大差值 , 如果|a[0] - a[n - 1]| <= k,则i , j 随便取都不可能a[i] - a[j]的绝对值大于k。

重点来来来来来了：我i , j 可以随便取，只需要满足i < j，那我让i = n - 2 , j = n - 1.在没排序的情况下我可以让i, j 等于任意两个数的下标，所以排序之后不影响i,j的取值

那最大价值一定是**min(a[n - 2] , a[n - 1])**就行。