Description of topic
The first solution: brute force solution, directly traversing all possible reverse pairs, and then check whether they meet the requirements of reverse pairs. This method only needs two layers of for loops to complete, but when the sequence length is very long, it runs It takes a long time to get the correct result, and the efficiency of the algorithm is very low. There is a running time limit on oj. Using the test set test program given by it, the correct result must be run within 1 second, so although this solution can be obtained The correct result is obtained but it fails to run on oj, but this solution is easier for beginners to understand the programming language. The following is the code to solve this problem with the violent solution method:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define N 100
int main()
{
int n; //represents the number of elements in the sequence
int count; //Record the number of reversed pairs
int array[N];
while (scanf("%d", &n) != EOF)
{
for (int k = 0; k < n; k ++ )
{
scanf("%d", &array[k]);
}
count = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = i + 1; j < n; j + + )
{
if (array[i] > array[j])
{
count + + ;
}
}
}
printf("%d\\
", count);
}
return 0;
\t
}
Screenshot of the running result:
The second method: divide and conquer, this question is exactly the same as the algorithm idea of using the divide and conquer method to realize the two-way merge sort. For the two-way merge sort, it needs to be compared one by one, and the reverse order Pairs also need to be compared one by one. In the process of one-to-one comparison, check whether each pair meets the requirements of reverse order pairs. If it is satisfied, the number of reverse order pairs will increase by one. Therefore, we can use this similarity to merge and sort the two-way The algorithm idea is applied to this problem of reverse order pair. If you don’t understand the two-way merge sort algorithm or the divide and conquer method, you can read this blog post. Tao program can understand, blog link: http://t.csdn.cn/W8W98
Algorithm idea:
First define a function Numcloseseq, which is used to calculate the number of reverse order pairs in two adjacent subsequences, but this algorithm is based on the fact that both the left subsequence and the right subsequence are ordered sequences. When the right subsequences are all ordered, if the number at the position with subscript i in the left subsequence is greater than the number at the position with subscript j in the right subsequence, then the number at the position after i in the left subsequence The elements are larger than the elements in the right subsequence before j, so there is no need to compare every possible reverse order pair like a violent solution, and the algorithm efficiency will be improved. When the number of elements in the sequence is large, this The time efficiency of the algorithm will be much more efficient than the brute force algorithm, so in this comparison process, we not only need to compare and record the number of reversed pairs in the two subsequences, but also combine the two subsequences into a larger The ordered sequence, so that it is still in order when it is used next time.
//This function is used to calculate the number of reversed pairs of two adjacent sequences, and return the number of reversed pairs using the function return value
void NumCloseSeq(unsigned long *array, unsigned low, unsigned mid, unsigned high, unsigned n) //The basis of this algorithm is based on the order of two subsequences, so it is still necessary to sort the two sequences
{
unsigned k = 0,i,j;
unsigned right = 0; //Record how many elements in the right subsequence have entered the address pointed to by temp;
for ( i = low, j = mid + 1; i <= mid & amp; & amp; j <= high;)
{
if (array[i] > array[j])
{
temp[k] = array[j];
right + + ;
j + + ;
k++;
\t\t\t
}
else
{
temp[k] = array[i];
count = count + right;
i + + ;
k++;
}
}
if (i > mid)
{
for (; j <= high; j ++ )
{
temp[k] = array[j];
k++;
}
}
else if (j > high)
{
for (; i <= mid; i ++ )
{
temp[k] = array[i];
k++;
count = count + right;
}
}
\t
for ( i = low, j = 0; i <= high; i + + , j + + )
{
array[i] = temp[j];
}
}
Define a function to record the number of reverse pairs in a merge sort:
//This function is used to calculate the number of reverse order pairs in a merge sort
void OneMergeNum(unsigned long *array, unsigned length, unsigned n)
{
//The number of subsequences to be compared in this merge sort is n/length or n/length + 1. It should also be noted that when the number of subsequences to be compared is odd, the last Subsequences are not compared
//Compared in pairs from left to right, the number of cycles required is the number of subsequences to be compared divided by 2 and rounded down
unsigned low, mid, high, numsubseq;
if (n % length)
{
numsubseq = n / length + 1;
}
else
{
numsubseq = n / length;
}
for (int i = 0; i < numsubseq / 2; i ++ )
{
low = i * 2 * length;
mid = low + length - 1;
high = low + 2 * length - 1;
if (high >= n)
{
high = n - 1;
}
NumCloseSeq(array, low, mid, high, n);
}
}
Finally, a function is defined to record the number of all reversed pairs when the entire merge sort is completed. Here, the functions of the two functions defined above are needed to assist in completing the definition of this function:
//This function is used to complete all the merge sorting. During this process, the number of reverse order pairs is recorded. It needs to use the functions of the two functions defined above to assist in the completion
void NumMerge(unsigned long *array, unsigned n)
{
unsigned length;
for (length = 1; length < n; length = 2 * length)
{
OneMergeNum(array, length, n);
}
}
Complete program source code and screenshots of running results:
Program source code:
//Using the idea of merge sorting to complete the reverse sequence pair, the sorting process is a process of pairwise comparison, and the reverse sequence pair also requires pairwise comparison #define _CRT_SECURE_NO_WARNINGS #include#include double count = 0; unsigned long array[500000] = { 0 }; unsigned long temp[500000] = { 0 }; //This function is used to calculate the number of reversed pairs of two adjacent sequences, and return the number of reversed pairs using the function return value void NumCloseSeq(unsigned long *array, unsigned low, unsigned mid, unsigned high, unsigned n) //The basis of this algorithm is based on the order of two subsequences, so it is still necessary to sort the two sequences { unsigned k = 0,i,j; unsigned right = 0; //Record how many elements in the right subsequence have entered the address pointed to by temp; for ( i = low, j = mid + 1; i <= mid & amp; & amp; j <= high;) { if (array[i] > array[j]) { temp[k] = array[j]; right + + ; j + + ; k++; \t\t\t } else { temp[k] = array[i]; count = count + right; i + + ; k++; } } if (i > mid) { for (; j <= high; j ++ ) { temp[k] = array[j]; k++; } } else if (j > high) { for (; i <= mid; i ++ ) { temp[k] = array[i]; k++; count = count + right; } } \t for ( i = low, j = 0; i <= high; i + + , j + + ) { array[i] = temp[j]; } } //This function is used to find the number of reverse pairs in a merge sort void OneMergeNum(unsigned long *array, unsigned length, unsigned n) { //The number of subsequences to be compared in this merge sort is n/length or n/length + 1. It should also be noted that when the number of subsequences to be compared is odd, the last Subsequences are not compared //Compared in pairs from left to right, the number of cycles required is the number of subsequences to be compared divided by 2 and rounded down unsigned low, mid, high, numsubseq; if (n % length) { numsubseq = n / length + 1; } else { numsubseq = n / length; } for (int i = 0; i < numsubseq / 2; i ++ ) { low = i * 2 * length; mid = low + length - 1; high = low + 2 * length - 1; if (high >= n) { high = n - 1; } NumCloseSeq(array, low, mid, high, n); } } //This function is used to complete all the merge sorting. During this process, the number of reverse order pairs is recorded. It needs to use the functions of the two functions defined above to assist in the completion void NumMerge(unsigned long *array, unsigned n) { unsigned length; for (length = 1; length < n; length = 2 * length) { OneMergeNum(array, length, n); } } int main() { unsigned n; scanf("%u", &n); count = 0; for (unsigned int i = 0; i < n; i ++ ) { scanf("%lu", &array[i]); } NumMerge(array, n); printf("%.0lf\\ ", count); }
Screenshot of running results: 
If you don't understand the implementation ideas of the algorithm topics that appear in the blog post, you can ask me privately, and I will reply after seeing it! ! !