hdu 1394

树状数组，优化查询
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn=5000+10;
 6 int n;
 7 int a[maxn],c[maxn];
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 int query(int x)
13 {
14     int sum=0;
15     while(x)
16     {
17         sum+=c[x];
18         x-=lowbit(x);
19     }
20     return sum;
21 }
22 void update(int x,int v)
23 {
24     while(x<=n)
25     {
26         c[x]+=v;;
27         x+=lowbit(x);
28     }
29 }
30 int main()
31 {
32     while(~scanf("%d",&n))
33     {
34         int i;
35         for(i=0;i<n;i++)
36         {
37             scanf("%d",&a[n-i-1]);
38             a[n-i-1]++;
39         }
40         int ans=0;
41         memset(c,0,sizeof(c));
42         for(i=0;i<n;i++)
43         {
44             ans+=query(a[i]);
45             update(a[i],1);
46         }
47         int minv=ans;
48         for(i=0;i<(n-1);i++)
49         {
50             ans=ans+2*a[i]-n-1;//因为是连续的很容易通过上一个算出本次的逆序对数
51             if(ans<minv) minv=ans;
52         }
53         printf("%d\n",minv);
54     }
55     return 0;
56 }