Minimum Inversion Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17870 Accepted Submission(s): 10851
Problem Description
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
Input
Output
Sample Input
Sample Output
逆序数的概念： 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个 逆序 。一个排列中逆序的总数就称为这个排列的 逆序数 。逆序数为 偶数 的排列称为 偶排列 ；逆序数为奇数的排列称为 奇排列 。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。
逆序数计算方法是：在逐个元素读取原始数列时，每次读取都要查询当前已读取元素中大于当前元素的个数，加到sum里，最后得到的sum即为原始数列的逆序数。
接下来找数列平移后得到的最小逆序数，假设当前序列逆序数是sum，那么将a[0]移到尾部后逆序数的改变是之前比a[0]大的数全部与尾部a[0]组合成逆序数，假设数量为x,则x=n-1-a[0]，而之前比a[0]小的数（也就是之前能和a[0]组合为逆序数的元素）不再与a[0]组合成逆序数，假设数量为y,则y=n-x-1，这样，新序列的逆序数就是sum+x-y=sum-2*a[0]+n-1;
接下来说明下线段树的作用，线段区间表示当前已读取的元素个数，比如[m,n]表示在数字m到n之间有多少个数已经读入，build时所有树节点全部为0就是因为尚未读数，ins函数是将新读入的数字更新到线段树里，点更新，query函数是查询当前数字区间已存在的数字个数。
除去逆序数方面的内容，这基本就是一道线段树的模板题
//2016.8.10
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 5005
#define lson (id<<1)
#define rson ((id<<1)|1)
#define mid ((l+r)>>1) using namespace std; struct node
{
int sum;
}tree[N*]; int arr[N]; void build_tree(int id, int l, int r)
{
tree[id].sum = ;
if(l == r){
return ;
}
build_tree(lson, l, mid);
build_tree(rson, mid+, r);
return;
} void ins(int id, int l, int r, int pos)
{
if(l == r){
tree[id].sum = ;return ;
}
if(pos <= mid)
ins(lson, l, mid, pos);
else
ins(rson, mid+, r, pos);
tree[id].sum = tree[lson].sum + tree[rson].sum;
return ;
} int query(int id, int l, int r, int ql, int qr)
{
if(ql<=l&&r<=qr){
return tree[id].sum;
}
int cnt = ;
if(ql<=mid)cnt += query(lson, l, mid, ql, qr);
if(mid+<=qr)cnt += query(rson, mid+, r, ql, qr); return cnt;
} int main()
{
int n;
while(cin>>n)
{
int sum = ;
build_tree(, , n-);
for(int i = ; i < n; i++){
scanf("%d", &arr[i]);
sum+=query(, , n-, arr[i], n-);
ins(, , n-, arr[i]);
}
//得到初始序列的逆序数
int ans = sum;
for(int i = ; i < n; i++)//移动数列找最小逆序数
{
sum = sum-*arr[i]+n-;
if(ans > sum)ans = sum;
}
cout<<ans<<endl;
} return ;
}
树状数组
//2016.9.13
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 5005 using namespace std; int a[N], arr[N], n; int lowbit(int x){return x&(-x);} void add(int pos, int tt)
{
for(int i = pos; i <= n; i+=lowbit(i))
arr[i] += tt;
} int query(int pos)
{
int sum = ;
for(int i = pos; i > ; i-=lowbit(i))
sum += arr[i];
return sum;
} int main()
{
int sum, ans, tmp;
while(scanf("%d", &n)!=EOF)
{
memset(arr, , sizeof(arr));
for(int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
a[i];
}
sum = ;
for(int i = ; i <= n; i++)
{
sum += query(n-a[i]);//n-a[i]表示a[i]为第n-a[i]大
add(n-a[i], );
}
ans = sum;
for(int i = ; i < n; i++)
{
add(n-a[i], -);
sum = sum+query(n-a[i])-a[i];
add(n-a[i], );
if(ans > sum) ans = sum;
}
printf("%d\n", ans);
} return ;
}