数码公司网站建设的意义,怎么用国外的服务器做网站,精准营销公司,网站建设需求说明考虑1,2,…,n (n 100000)的排列i1#xff0c;i2#xff0c;…#xff0c;in#xff0c;如果其中存在j,k#xff0c;满足 j k 且 ij ik#xff0c; 那么就称(ij,ik)是这个排列的一个逆序。 一个排列含有逆序的个数称为这个排列的逆序数。例如排列 26345…考虑1,2,…,n (n 100000)的排列i1i2…in如果其中存在j,k满足 j k 且 ij ik 那么就称(ij,ik)是这个排列的一个逆序。 一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个 逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)因此该排列的逆 序数就是8。 现给定1,2,…,n的一个排列求它的逆序数 分治归并做到O(nlogn) 1 将数组分成两半分别求出左半边的逆序数和右半边的逆序数 2 再算有多少逆序是由左半边取一个数和右半边取一个数构成(要求O(n)实 现
2的关键左半边和右半边都是排好序的。比如都是从大到小排序的。这 样左右半边只需要从头到尾各扫一遍就可以找出由两边各取一个数构成的 逆序个数
#include iostream
#include string.h
#include stdio.husing namespace std;
const int N 1005;int a[N],tmp[N];
int ans;void Merge(int l,int m,int r)
{int i l;int j m 1;int k l;while(i m j r){if(a[i] a[j]){tmp[k] a[j];ans m - i 1;}else tmp[k] a[i];}while(i m) tmp[k] a[i];while(j r) tmp[k] a[j];for(int il;ir;i)a[i] tmp[i];
}void Merge_sort(int l,int r)
{if(l r){int m (l r) 1;Merge_sort(l,m);Merge_sort(m1,r);Merge(l,m,r);}
}int main()
{int n,T,tt1;scanf(%d,T);while(T--){scanf(%d,n);for(int i0;in;i)scanf(%d,a[i]);ans 0;Merge_sort(0,n-1);printf(Scenario #%d:\n%d\n\n,tt,ans);}return 0;
}
