首页 > 代码库 > HDU 1394 Minimum Inversion Number
HDU 1394 Minimum Inversion Number
C - Minimum Inversion Number
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
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
题目大意为 有n个从0到n 的数 按照给定次序排列 每次只能将最前的一个数移到末尾 算出每种情况的逆序数 并求出逆序数最小值
这道题属于 归并排序的应用
首先 我们把当前情况下的逆序数求出
然后循环n次 每次最前一个往最后移 则 ans=ans+ (n-1+a[i])-a[i]
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int num[ 5000+10],a[5000+10];int vis[5000+10];int ans;void Merge(int begin,int mid,int end){ int i=begin,j=mid+1,k=begin; while(i<=mid&&j<=end) { if(a[i]<=a[j]) vis[k++]=a[i++]; else { ans+=mid-i+1; vis[k++]=a[j++]; } } while(i<=mid) { vis[k++]=a[i++]; } while(j<=end) { vis[k++]=a[j++]; } for(i=begin;i<=end;i++) { a[i]=vis[i]; }}void mergesort(int begin,int end){ if(begin!=end) { int mid=(begin+end)/2; mergesort(begin,mid); mergesort(mid+1,end); Merge(begin,mid,end); }}int main(){ int n,i,j,minn; while(scanf("%d",&n)!=EOF) { ans=0; for(i=1;i<=n;i++) {scanf("%d",&a[i]); num[i]=a[i];} mergesort(1,n); minn=ans; for(i=1;i<n;i++) { ans=ans+n-1-2*num[i]; if(ans<minn) minn=ans; } cout<<minn<<endl; } return 0;}