首页 > 代码库 > Minimum Inversion Number 【线段数】
Minimum Inversion Number 【线段数】
Problem Description
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
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
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
来源： http://acm.hdu.edu.cn/showproblem.php?pid=1394
大意：给出一个从0到n-1的序列，逐次把首数字移到尾部，问，最小逆序数？
题解：
这里的逆序数和线性代数中的逆序数是一个概念，某个数前面出现比其大的数，称为逆序，总序列中逆序的个数，称为逆序数。
用线段树求第一次输入的序列的逆序数，然后用公式来遍历所有转移情况。
#include<stdio.h>
#include<string.h>
#include<string.h>
#include<algorithm>
#define M 5001
using namespace std;
struct Node{
int a;
int b;
int sum;
}t[3*M];
int p[M],total;
/*
创建范围为x~y的线段树
*/
void make(int x,int y,int n){
t[n].a = x;
t[n].b = y;
t[n].sum = 0;
if(x != y){
int mid = (x + y)/2;
make(x,mid,2*n);
make(mid+1,y,2*n+1);
}
}
/*
返回 x~y 区间内的个数sum
*/
int query(int x,int y,int n){
if(x <= t[n].a && y >= t[n].b){
return t[n].sum;
}else{
int mid = (t[n].a + t[n].b)/2;
if(x > mid){
query(x,y,2*n+1);
}else if( y <= mid){
query(x,y,2*n);
}else{
return query(x,y,2*n)+query(x,y,2*n+1);
}
}
}
/*
从最高级区间开始往下面的具有x的区间的sum
*/
void update(int x,int n){
t[n].sum++;
if(t[n].a == x && t[n].b == x){
return;
}
int mid = (t[n].a + t[n].b)/2;
if(x > mid){
update(x,2*n+1);
}else{
update(x,2*n);
}
}
int main(){
int n,m,a[M];
while(~scanf("%d",&n)){
make(0,n-1,1);
int total = 0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
total += query(a[i],n-1,1);
update(a[i],1);
}
int ans = total;
for(int i=0;i<n;i++){
total = total - a[i] + (n - a[i] - 1);
ans = min(ans,total);
}
printf("%d\n",ans);
}
return 0;
}
/*
total = total - a[i] + (n - a[i] - 1);
比如1 3 6 9 0 8 5 7 4 2
比1小的数有0个，后面比1大的数有8个，1放到后面，少了1个逆序数，又多了8个逆序数
比3小的数有3个，后面比3大的数有6个，3放到后面，少了3个逆序数，又多了6个逆序数
。。。
*/
Minimum Inversion Number 【线段数】