Dan robocontest javoblari



Yüklə 0,58 Mb.
səhifə4/7
tarix07.01.2024
ölçüsü0,58 Mb.
#204426
1   2   3   4   5   6   7
2 5411487045807781686

85-masala
#include

using namespace std;


#define int long long

int _mergeSort(int arr[], int temp[], int left, int right);

int merge(int arr[], int temp[], int left, int mid,

int right);


/* This function sorts the

input array and returns the

number of inversions in the array */

int mergeSort(int arr[], int array_size)

{


int temp[array_size];

return _mergeSort(arr, temp, 0, array_size - 1);

}

/* An auxiliary recursive function

that sorts the input array and

returns the number of inversions in the array. */

int _mergeSort(int arr[], int temp[], int left, int right)

{


int mid, inv_count = 0;

if (right > left) {

/* Divide the array into two parts and

call _mergeSortAndCountInv()

for each of the parts */

mid = (right + left) / 2;


/* Inversion count will be sum of

inversions in left-part, right-part

and number of inversions in merging */

inv_count += _mergeSort(arr, temp, left, mid);

inv_count += _mergeSort(arr, temp, mid + 1, right);


/*Merge the two parts*/

inv_count += merge(arr, temp, left, mid + 1, right);

}


return inv_count;

}

/* This function merges two sorted arrays

and returns inversion count in the arrays.*/

int merge(int arr[], int temp[], int left, int mid,

int right)

{

int i, j, k;



int inv_count = 0;

i = left; /* i is index for left subarray*/

j = mid; /* j is index for right subarray*/

k = left; /* k is index for resultant merged subarray*/

while ((i <= mid - 1) && (j <= right)) {

if (arr[i] <= arr[j]) {

temp[k++] = arr[i++];

}


else {

temp[k++] = arr[j++];


/* this is tricky -- see above

explanation/diagram for merge()*/

inv_count = inv_count + (mid - i);

}

}



/* Copy the remaining elements of left subarray

(if there are any) to temp*/

while (i <= mid - 1)

temp[k++] = arr[i++];


/* Copy the remaining elements of right subarray

(if there are any) to temp*/

while (j <= right)

temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/

for (i = left; i <= right; i++)

arr[i] = temp[i];


return inv_count;

}

// Driver code

main()

{
int t; cin>>t;


while(t--){
int n;cin>>n;
int arr[n];
for(int i=0;i>arr[i];
int ans = mergeSort(arr, n);

cout << ans<
}
return 0;

}


Yüklə 0,58 Mb.

Dostları ilə paylaş:
1   2   3   4   5   6   7




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin