英文网站建设成都,桔子建站官网,云龙微网站开发,网站模板能上传图片逆序对定义#xff1a;对于一个包含N个非负整数的数组A[1..n]#xff0c;如果有i j#xff0c;且A[ i ]A[ j ]#xff0c;则称(A[ i] ,A[ j] )为数组A中的一个逆序对。 常见的两种方法求解逆序对#xff1a;1.穷举法#xff08;暴力求解#xff09;#xff0c…逆序对定义对于一个包含N个非负整数的数组A[1..n]如果有i j且A[ i ]A[ j ]则称(A[ i] ,A[ j] )为数组A中的一个逆序对。 常见的两种方法求解逆序对1.穷举法暴力求解时间复杂度On^2。2.归并法 时间复杂度Onlogn。 穷举法对于一个给定的序列依次从左往右取每一个元素从该元素右边第一个元素开始向右扫描遇到比它小的元素则计数1直到处理完整个序列。 #include iostream#include cstdlib#include cstdio using namespace std; #define MAXN 1000int num[MAXN];int sum 0; void solve(int n){ for(int i 0; i n; i) for(int j i1; j n; j){ if(num[i] num[j])sum;}} int main(int argc, char const *argv[]){ int n; scanf(%d, n); for(int i 0; i n; i) scanf(%d, num[i]);solve(n); printf(%d\n, sum); return 0;} 归并法将序列A[l..r]分成两半A[l..mid]和A[mid1..r]分别进行归并排序然后再将这两半合并起来。 在合并的过程中设limidmid1jr当A[i]A[j]时不产生逆序数当A[i]A[j]时在 前半部分中比A[i]大的数都比A[j]大所以将A[j]放在A[i]前面的话逆序数要加上mid1-i。因此可以在归并排序中的合并过程中计算逆序数。 #include iostream#include cstdlib#include cstdio using namespace std; #define MAXN 1000int num[MAXN], temp[MAXN];int sum 0; void Merge(int l, int mid, int r){ int i l, j mid1, k l; while(i mid j r){ if(num[i] num[j]){temp[k] num[j];sum mid-i1;//产生逆序对} elsetemp[k] num[i];} while(i mid)temp[k] num[i]; while(j r)temp[k] num[j]; for(int i l; i r; i)num[i] temp[i]; } void Merge_sort(int l, int r){ if(l r){ int mid l (r-l)/2;//可防止加法溢出Merge_sort(l, mid);//左边Merge_sort(mid1, r);//右边Merge(l, mid, r);//合并} } int main(int argc, char const *argv[]){ int n; scanf(%d, n); for(int i 0; i n; i) scanf(%d, num[i]);Merge_sort(0, n-1); printf(%d\n, sum); return 0;}附上POJ逆序对的一道测试题http://poj.org/problem?id1804
