CFR 713 C. Sonya and Problem Wihtout a Legend ( Priority Queue + Median + Smaller to Larger )

Problem - 713C - Codeforces
題意：
給一組數列，每次操作可以將一個數字增加或減少 1，求最少的操作數，使得數列嚴格遞增。
解法：
首先看到嚴格遞增，將每個數字減去自己的下標後，就可以轉換成非嚴格遞增，題目或許會比較好解。接著考慮，如果有幾個數字，都合法，但這時候突然在它們後面出現了一個很小的數，需要多少花費？此時轉換成一維距離的問題，顯然把所有數字換成中位數就好。因此得到結論，從前面考慮過去，每次新增元素時，如果產生逆序就快速地將會產生逆序的部分所有數變換成它們的中位數。中位數可以利用兩個優先佇列做動態插入和查詢，一個大根堆，一個小根堆，輕鬆的。合併時可以考慮用啟發式合併，編程複雜度不高。

typedef priority_queue<int> gpq;
typedef priority_queue<int, vi, greater<int> > lpq;

int N;
vi _A;

void init() {
  cin >> N;
  _A = vi(N);
  for (int i = 0; i < N; ++i) cin >> _A[i];
}

vi A;

void preprocess() {
  A = vi(N);
  for (int i = 0; i < N; ++i) A[i] = _A[i] - i;
}

void merge(tuple<gpq, lpq>& a, tuple<gpq, lpq>& b) {
  if (not(get<0>(a).size() + get<1>(a).size() >=
          get<0>(b).size() + get<1>(b).size()))
    swap(a, b);
  while (not get<0>(b).empty()) {
    int u = get<0>(b).top();
    get<0>(b).pop();
    if (u <= get<0>(a).top())
      get<0>(a).emplace(u);
    else
      get<1>(a).emplace(u);
  }
  while (not get<1>(b).empty()) {
    int u = get<1>(b).top();
    get<1>(b).pop();
    if (u <= get<0>(a).top())
      get<0>(a).emplace(u);
    else
      get<1>(a).emplace(u);
  }
  while (abs((int)get<0>(a).size() - get<1>(a).size()) > 1) {
    if (get<0>(a).size() < get<1>(a).size())
      get<0>(a).emplace(get<1>(a).top()), get<1>(a).pop();
    else
      get<1>(a).emplace(get<0>(a).top()), get<0>(a).pop();
  }
}

int get_median(tuple<gpq, lpq>& t) {
  gpq& a = get<0>(t);
  lpq& b = get<1>(t);
  if (a.size() > b.size()) return a.top();
  return b.top();
}

void solve() {
  vector<tuple<gpq, lpq> > seq;
  for (int i = 0; i < N; ++i) {
    gpq a;
    lpq b;
    a.emplace(A[i]);
    seq.emplace_back(a, b);
    while (seq.size() >= 2 and
           get_median(seq[(int)seq.size() - 2]) > get_median(seq.back()))
      merge(seq[(int)seq.size() - 2], seq.back()), seq.pop_back();
  }
  ll ans = 0;
  for (int i = 0, ptr = 0; ptr < seq.size(); ++ptr) {
    int med = get_median(seq[ptr]);
    int sz = get<0>(seq[ptr]).size() + get<1>(seq[ptr]).size();
    for (int j = 0; j < sz; ++j) ans += abs(A[i + j] - med);
    i += sz;
  }
  cout << ans << endl;
}