站外题贪心求证（悬三关）

题目大意：

给定一个长度为

n

的数组

a

，你可以将任意数加一，不限次数，求最终排列里的逆序对的最少数量。

思路：

先离散化，如果

a_i

加一，那么逆序对的数量必然会增加减少等于

a_i+1

的数的个数（设其为

fr_i

），增加后面等于

a_i

的数的个数（设其为

bc_i

），贪心如果

fr_i>bc_i

，那么将

a_i

加一，初始逆序对用树状数组维护。

代码：

CPP

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<LL, LL>;

const LL kMaxN = 1e6 + 5;

LL n, idx, ans, a[kMaxN], fr[kMaxN], bc[kMaxN], b[kMaxN], cnt[kMaxN];

template <class T>
struct BIT {
  T c[kMaxN] = {0};
  T query(LL x) {
    T sum = 0;
    for (; x; x -= x & -x) {
      sum += c[x];
    }
    return sum;
  }
  void update(LL x, T s) {
    for (; x <= 2e5; x += x & -x) {
      c[x] += s;
    }
  }
};

signed main() {
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
    b[++idx] = a[i];
  }
  sort(b + 1, b + idx + 1);
  for (LL i = 1; i <= n; i++) {
    a[i] = lower_bound(b + 1, b + idx + 1, a[i]) - b;
  }
  for (LL i = n; i; i--) {
    bc[i] = cnt[a[i]], cnt[a[i]]++;
  }
  memset(cnt, 0, sizeof cnt);
  BIT<LL> tr;
  for (LL i = 1; i <= n; i++) {
    ans += i - 1 - tr.query(a[i]);
    tr.update(a[i], 1);
  }
  for (LL i = 1; i <= n; i++) {
    fr[i] = cnt[a[i] + 1];
    if (fr[i] > bc[i]) {
      ans = ans - fr[i] + bc[i];
    }
    cnt[a[i] + (fr[i] > bc[i])]++;
  }
  cout << ans;
  return 0;
}

当然巨佬们有更好解法发在楼下。

站外题贪心求证（悬三关）

讨论操作

回复

相关推荐

站外题贪心求证（悬三关）