哈理工oj 1250Minimum Inversion Number解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1250

这道题是求最小逆序数的题，用树状数组和线段树都可以解决，其实最耗费时间的是求原序列的逆序数的部分

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 5005
 4 int a[N];
 5 int v[N];
 6 int n;
 7 int lowbit(int x)
 8 {
 9     return x&-x;
10 }
11 int min(int a,int b)
12 {
13     return a<b?a:b;
14 }
15 void add(int x)
16 {
17     while(x<=n)
18     {
19         a[x]++;
20         x+=lowbit(x);
21     }
22 }
23 int getsum(int x)
24 {
25     int sum=0;
26     while(x>=1)
27     {
28         sum+=a[x];
29         x-=lowbit(x);
30     }
31     return sum;
32 }
33 int main()
34 {
35     int i,sum;
36     while(scanf("%d",&n)!=EOF)
37     {
38         sum=0;
39         memset(a,0,sizeof(a));
40         for(i=0;i<n;i++)
41         {
42             scanf("%d",&v[i]);
43             v[i]++;//因为树状数组的下标从1开始，而输入序列是0-—n-1所以把整个数组右移
44             sum+=v[i]-1-getsum(v[i]-1);
45             add(v[i]);
46         }
47         int ans=sum;
48         for(i=0;i<n;i++)
49         {
50             sum+=(n-v[i])-(v[i]-1);
51             ans=min(ans,sum);
52         }
53         printf("%d\n",ans);
54     }
55     return 0;
56 }