Minimum Inversion Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 474 Accepted Submission(s): 217
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.
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
#include<stdio.h> struct Shu { int zuo; int you; int date; }shu[5000*3]; int p[5000+10]; void buildtree(int a,int b,int n=1) { shu[n].zuo=a; shu[n].you=b; shu[n].date=0; if(a==b)return; int zhong=(a+b)>>1; buildtree(a,zhong,2*n); buildtree(zhong+1,b,2*n+1); } void addtree(int a,int n=1) { shu[n].date++; if(shu[n].zuo==shu[n].you)return; int zhong=(shu[n].zuo+shu[n].you)>>1; if(a<=zhong)addtree(a,2*n); else addtree(a,2*n+1); } int findtree(int a,int b,int n=1) { if(shu[n].zuo==a&&shu[n].you==b)return(shu[n].date); int zhong=(shu[n].zuo+shu[n].you)>>1; if(b<=zhong)return(findtree(a,b,2*n)); else if(a>zhong)return(findtree(a,b,2*n+1)); else return(findtree(a,zhong,2*n)+findtree(zhong+1,b,2*n+1)); } int main() { // freopen("in.txt","r",stdin); int min; int n; int sum; int i; while(scanf("%d",&n)!=EOF) { buildtree(0,n-1); sum=0; for(i=0;i<n;i++) { scanf("%d",&p[i]); sum+=findtree(p[i],n-1); addtree(p[i]); } min=sum; for(i=0;i<n-1;i++) { sum=sum+n-1-2*p[i]; if(sum<min)min=sum; } printf("%d\n",min); } return(0); }
相关推荐
a[j] 则称 i j 为a数组的一个逆序对(inversion) 比如<2 3 8 6 1>有5个逆序对 请考虑一个最坏情况O nlogn 的算法确定n个元素的逆序对数目 注意此题请勿用O n^2 的简单枚举去实现 输入格式 第一行:n ...
基于最小支撑梯度的二维大地电磁正则化反演,向阳,于鹏,大地电磁反演一般是不适定的,通常采用正则化反演的方法加入模型约束来减小反演结果的非唯一性,从而得到较为稳定的反演结果。目
设a[0…n-1]是一个包含n个数的数组,若在i的情况下,有a[i]>a[j],则称(i, j)为a数组的一个逆序对(inversion)。 比如 ,3,8,6,1> 有5个逆序对。请采用类似“合并排序算法”的分治思路以O(nlogn)的效率来实现逆序对...
设a[0…n-1]是一个包含n个数的数组,若在i的情况下,有a[i]>a[j],则称(i, j)为a数组的一个逆序对(inversion)。 比如 ,3,8,6,1> 有5个逆序对。 请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。 注意此...
To calculate square Matrix inversion...
gravity 2D inversion
GAN Inversion A Survey.pdf
矩阵求逆c语言算法!
inversion non-linear
geophysical-inversion-for-mineral-exploration
给定一个数N(i.e.12),N=abs(N-reverse_N). (i.e, abs(12-21))在第几轮后N=0.
从键盘输入一个字符串 然后用程序实现字符串的逆序操作
使用DSP在LTE MIMO中计算矩阵逆运算
full_waveform_inversion is good to velocity model building.
Inversion of Control Containers and the Dependency Injection pattern(中文版)
希尔伯特空间中Moore-Penrose广义逆的二层条件数,刁怀安,魏益民,条件数理论是数值分析中的一个重要研究课题,它能揭示问题对于输入数据的敏感性。当一个问题的条件数很大时,该问题称为不适定问
City Thermal Inversion.zip
翻译1Inversion.pptx
Matlab_inversion_inversion_光谱反演模型_matlab_yet2s
Here is an Inversion program with only 1 line of code to change a picture to a negative format.