rt

如何从这个式子化简得到可以交换两个点的条件的

|a[j+1]-a[j-1]-c| + |a[j]-a[i-1]-c| + |a[i]-a[j]-c| = |a[i]-a[i-1]-c| + |a[j+1]-a[j]-c| + |a[j]-a[j-1]-c|

(a[j+1] <= a[j] <= a[j-1] <= a[i] <= a[i-1])
c < 0

官方题解的证明看不懂，百度翻译太生草了

(看不懂我的式子可以结合我F1的代码理解)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 5;

int a[MAXN], n, c;

bool cmp(int a, int b) {
  return a > b;
}

long long Abs(const long long x) {
  return x > 0 ? x : -x;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> c;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    if (c >= 0) {
      sort(a, a + n);
      for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
      }
      cout << '\n';
    } else {
      long long minans = 0;
      sort(a, a + n, cmp);
      for (int i = 1; i < n - 1; ++i) {
        int _j = -1;
        for (int j = n - 2; j > i; --j) {
          long long v;
          v = Abs(a[j + 1] - a[j - 1] - c) + Abs(a[j] - a[i - 1] - c) + Abs(a[i] - a[j] - c);
          v -= Abs(a[i] - a[i - 1] - c) + Abs(a[j + 1] - a[j] - c) + Abs(a[j] - a[j - 1] - c);
          if (!v) {
            _j = j;
            break;
          }
        }
        for (int j = _j; j > i; --j) {
          swap(a[j], a[j - 1]);
        }
      }
      for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
      }
      cout << '\n';
    }
  }
  return 0;
}