HDU 1394 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
二、题目大意：
把一个数组的前m项依次放到最后面，形成n个数组，问这其中逆序对最少的那个的逆序对是多少。
三、思路：先求不变化前的逆序对，然后枚举所有n个数组，求最小逆序对
1、处理要将arr[i]++使得0变成1
2、从左到右插入，sum(arr[i])为左边比arr[i]小的元素和，那么(sum(n)-sum(arr[i]))就是左边比它大的，也就是逆序对个数了。
3、枚举所有数组，邝斌大神说n+1-arr[i]为此时增加逆序对数，arr[i]为减少逆序对数，恩就是这样。所以he+=(n+1-arr[i]-arr[i]);然后取其中最小的就可以啦~！
四、实现：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define mem(arr,val) memset((arr),(val),(sizeof (arr)))
#define ll long long
#define N 5010
using namespace std;
int c[N];
int arr[N];
int lowbit(int x)
{
return x&(-x);
}
int sum(int i)
{
int ans=0;
while(i>0)
{
ans+=c[i];
i-=lowbit(i);
}
return ans;
}
void updata(int i,int val)
{
while(i<=N)
{
c[i]+=val;
i+=lowbit(i);
}
}
int main()
{
// freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n)!=EOF)
{
mem(c,0);
int he=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
arr[i]++;//处理0
he+=(sum(n)-sum(arr[i]));
updata(arr[i],1);
}
int ansmin=he;
for(int i=1;i<=n;i++)
{
he+=(n+1-arr[i]-arr[i]);
if(he<ansmin)
ansmin=he;
}
printf("%d\n",ansmin);
}
return 0;
}