c++ - 为什么这个计数器是这样增加的，而不是在这个分而治之的算法中一个一个增加？

Question

我正在阅读以下问题的算法解决方案:

This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated. Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array. Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.

所以问题给了你文件，但这里是解决方案:

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#define SIZE 100000

using namespace std;

long long splitInv(long *arr, long l, long u)
{
     long *tarr = new long[u-l+2];
     long i=l, j=(u-l)/2+l+1, k;
     long long count=0;
     for(k=1; (k<=u-l+1) && (i<=(u-l)/2+l) && (j<=u); k++)
     {
              if(arr[i]<arr[j]) tarr[k]=arr[i++];
              else
              {
                  tarr[k]=arr[j++];
                  count=count+((u-l)/2+l-i+1);
              }
     }
     for(; k<=u-l+1 && i<=(u-l)/2+l; k++) tarr[k]=arr[i++];
     for(; k<=u-l+1 && j<=u; k++) tarr[k]=arr[j++];
     for(k=1, i=l ; k<=u-l+1 && i<=u; k++, i++) arr[i]=tarr[k];
     delete tarr;
     return count;
}

long long numInv(long *arr, long l, long u)
{
     if(u<=l) return 0;
     return numInv(arr, l, (u-l)/2+l) + numInv(arr, (u-l)/2+l+1, u) + splitInv(arr, l, u);
}

int main(int argc, char *argv[])
{
    long *arr=new long[SIZE+1];
    char a[10];
    FILE *f=fopen("IntegerArray.txt","r");
    for(long i=1; i<=SIZE; i++)
    {
            fgets(a,10,f);
            arr[i]=atol(a);
    }
    fclose(f);
    cout<<"Number of Inversions: "<<numInv(arr,1,SIZE)<<endl;
    delete arr;
    system("PAUSE");
    return EXIT_SUCCESS;
}

所以，我想知道为什么计数器是按以下方式增加而不是一个一个地增加，因为它只是在计算反转的次数:

count=count+((u-l)/2+l-i+1);

所以，对我来说应该是:

count=count+1;

Answer 1

如您所知，它使用的是分而治之算法，如果您的 if 条件不为真，它需要忽略前半部分，因此它必须按照您的程序所示偏移您的数组，而不是像您假设的那样。