алгоритм — C ++ Подсчет инверсий в массиве, Fatal Signal 11 (BIT)

Мне дали этот вызов в «классе» программирования. В конце концов я решил использовать решение «Binary Indexed Trees», так как о структурах данных мне хотелось бы узнать больше. Внедрение BIT было довольно простым, а после этого — не так много. Я столкнулся с «Фатальным сигналом 11» при загрузке решения на сервер, который, из того, что я прочитал, чем-то похож на исключение нулевого указателя. Не смог разобраться в проблеме, решил проверить Другой Решения с БИТ, но наткнулся на ту же проблему.

#include<iostream>
using namespace std;/*    <BLACK MAGIC COPIED FROM geeksforgeeks.org>     */
int getSum(int BITree[], int index){
int sum = 0;
while (index > 0){
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(int BITree[], int n, int index, int val){
while (index <= n){
BITree[index] += val;
index += index & (-index);
}
}
/*    <BLACK MAGIC COPIED FROM geeksforgeeks.org>     */int Count(int arr[], int x){
int sum = 0;
int biggest = 0;

for (int i=0; i<x; i++) {
if (biggest < arr[i]) biggest = arr[i];
}

int bit[biggest+1];

for (int i=1; i<=biggest; i++) bit[i] = 0;

for (int i=x-1; i>=0; i--)
{
sum += getSum(bit, arr[i]-1);
updateBIT(bit, biggest, arr[i], 1);
}
return sum;
}

int main(){
int x;
cin >> x;int *arr = new int[x];
for (int temp = 0; temp < x; temp++) cin >> arr[temp];

/*sizeof(arr) / sizeof(arr[0]); <-- someone suggested this,
but it doesn't change anything from what I can tell*/

cout << Count(arr,x);

delete [] arr;
return 0;
}

Я весьма озадачен этим. Это может быть просто какая-то простая вещь, по которой я скучаю, но я действительно не знаю. Любая помощь высоко ценится!

0

Решение

У вас есть условие, что каждое число лежит между 1 и 1018. Итак, ваш самый большой номер может быть 1018. Это слишком много для следующей строки:

int bit[biggest+1];
2

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

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector