对于计数反转对的问题，为什么这个稍微修改过的计数反转对逻辑不起作用？

Question

这是我用于计算反转对的代码，我已经修改了计算反转对的逻辑，但它不起作用，你能指出原因吗？

int cnt = 0;

void merge(vector<int> &a, int low, int mid, int high) {
  vector<int> temp;
  int left = low;
  int right = mid + 1;
  while (left <= mid && right <= high) {
    if (a[left] <= a[right]) {
      temp.push_back(a[left]);
      left++;
    } else {
      if (a[left] > 2 * a[right] && left <right) {
        cnt += mid - left + 1;
      }
      temp.push_back(a[right]);
      right++;
    }
  }

  while (left <= mid) {
    temp.push_back(a[left]);
    left++;
  }
  while (right <= high) {
    temp.push_back(a[right]);
    right++;
  }

  for (int i = low; i <= high; i++) {
    a[i] = temp[i - low];
  }
  for (int i = low; i <= high; i++) {
    cout << a[i] << " ";
  }
  cout << cnt << endl;
}

void mergesort(vector<int> &a, int low, int high) {
  if (low >= high)
    return;
  int mid = low + (high - low) / 2;
  mergesort(a, low, mid);
  mergesort(a, mid + 1, high);
  merge(a, low, mid, high);
}

int team(vector<int> &a, int n) {
  mergesort(a, 0, n - 1);
  return cnt;
}

为什么这不起作用测试用例 4 1 2 3 1 is 3 is am getting 2 的答案在此代码中？

Answer 1

代码有两个问题： 首先，你根本不需要

if (a[left] > 2 * a[right] && left <right)

条件。

a[left] > 2 * a[right]

看起来很奇怪，因为您需要知道

a[left]

> 或 < than

a[right]

的所有情况，并且这已经由 if 之前管理。在这里，值的两倍小或两倍应该无关紧要。第二个条件，

left <right

始终自动为真。请注意，

left

只能与

mid

一样大，并且

right

从

mid+1

开始。

其次，这个算法与你所想的相反地看问题。当你期待答案 3 时，意味着你想要向量排序为

4 3 2 1 1

；然而，在这里您将最小值放在第一位，因此它会将值排序为

1 1 2 3 4

。所以它不是 3，实际上是 6 个反转。

如果您希望它计算另一个方向的反转，您也需要反转您的比较：

if (a[left] <= a[right]) {

是正确的测试。 最终排序如下：

while (left <= mid && right <= high) {
    if (a[left] <= a[right]) {
      temp.push_back(a[left]);
      left++;
    } else {
      cnt += mid - left + 1;
      temp.push_back(a[right]);
      right++;
    }
  }

如果你想得到3作为回报。