hdu1394Minimum Inversion Number

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394

n-1-x[i]是x[i]后面比x[i]大的数的个数，x[i]是x[i]后面比[i]小的数的个数

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define lson l,m,rt<<1
 5 #define rson m+1,r,rt<<1|1
 6 
 7 const int maxn=5010;
 8 int f[maxn<<2];
 9 int x[maxn];
10 void pushup(int rt)
11 {
12     f[rt]=f[rt<<1]+f[rt<<1|1];
13 }
14 void build(int l,int r,int rt)
15 {
16     f[rt]=0;
17     if(l==r) {
18 
19         return ;
20     }
21     int m=(l+r)>>1;
22     build(lson);
23     build(rson);
24 }
25 
26 int query(int L,int R,int l,int r,int rt)
27 {
28     if(L<=l&&r<=R) return f[rt];
29     int m=(l+r)>>1;
30     int ans=0;
31     if(L<=m) ans+=query(L,R,lson);
32     if(m<R) ans+=query(L,R,rson);
33     return ans;
34 }
35 void update(int p,int l,int r,int rt)
36 {
37     if(l==r) {
38         f[rt]++;
39         return ;
40     }
41     int m=(l+r)>>1;
42     if(p<=m) update(p,lson);
43     else update(p,rson);
44     pushup(rt);
45 }
46 int main()
47 {
48     int n;
49     while(scanf("%d",&n)!=EOF)
50     {
51         build(0,n-1,1);
52         int res=0;
53         for(int i=0;i<n;i++)
54         {
55             scanf("%d",&x[i]);
56             res+=query(x[i],n-1,0,n-1,1);
57             update(x[i],0,n-1,1);
58         }
59         int ans=res;
60         for(int i=0;i<n;i++){
61                 ans+=n-x[i]-1-x[i];  //n-1-x[i]是x[i]后面比x[i]大的数的个数，x[i]是x[i]后面比[i]小的数的个数
62             res=min(ans,res);
63         }
64         printf("%d
",res);
65     }
66 }