Почему этот счетчик увеличивается таким образом, а не один за другим в этом алгоритме разделяй и властвуй?

Я читал алгоритм решения следующей проблемы:

Этот файл содержит все 100 000 целых чисел от 1 до 100 000 (включительно) в некотором порядке, без повторения целого числа.
Ваша задача состоит в том, чтобы вычислить количество инверсий в данном файле, где i-я строка файла указывает i-ю запись массива.
Из-за большого размера этого массива вы должны реализовать быстрый алгоритм «разделяй и властвуй», описанный в видео-лекциях.
Числовой ответ для данного входного файла должен быть напечатан в свободном месте ниже.

Таким образом, проблема дает вам файл, но вот решение:

#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;

0

Решение

Поскольку вы знаете, что он использует алгоритм «разделяй и властвуй», он должен игнорировать первую половину, если ваше условие if не истинно, поэтому он должен смещать ваш массив, как показано в вашей программе, а не так, как вы предполагаете.

0

Другие решения


По вопросам рекламы [email protected]