HDU 1394

单点，利用线段树解题，看到数据大小一定要敏感，说不定就是暗藏的解题思路
 1 #include <stdio.h>
 2 #define lson l,mid,id<<1
 3 #define rson mid+1,r,id<<1|1
 4 const int MM= 5001;
 5 int sum[MM<<2];
 6 
 7 void build_tree(int l,int r,int id)
 8 {
 9     sum[id]=0;
10     if(l==r)
11     {
12         return;
13     }
14     else
15     {
16         int mid=(l+r)>>1;
17         build_tree(lson);
18         build_tree(rson);
19     }
20     
21 }
22 int Query(int L,int R,int l,int r,int id)
23 {
24     if(L<=l&&r<=R)
25     {
26         return sum[id];
27     }
28     else
29     {
30         int mid=(l+r)>>1;int ret=0;
31         if(L<=mid)ret+=Query(L,R,lson);
32         if(R>mid)ret+=Query(L,R,rson);
33         return ret;
34     }
35 }
36 void update(int pos,int l,int r,int id)
37 {
38     if(l==r)
39     {
40         sum[id]++;return;
41     }
42     else{
43         int mid=(l+r)>>1;
44         if(pos<=mid)update(pos,lson);
45         if(pos>mid)update(pos,rson);
46         sum[id]=sum[id<<1]+sum[id<<1|1];
47     }
48 }
49 int main()
50 {
51     int n,i,seg[MM];
52     while(~scanf("%d",&n))
53     {
54         build_tree(0,n-1,1);
55         int ans=0;
56         for(i=0;i<n;i++)
57         {
58             scanf("%d",&seg[i]);
59             ans+=Query(seg[i],n-1,0,n-1,1);
60         /*
61             +比seg[i]大的数，按输入顺序，因为每个数都不会超过n,所以简单了许多
62         */
63             update(seg[i],0,n-1,1);
64         }
65         int min=ans;
66         for(i=0;i<n;i++)
67         {
68             ans+=n-seg[i]*2-1;
69             /*
70                 比seg[i]小的-seg[i],seg[i]移到最后，+(n-seg[i]-1)
71             */
72             if(ans<min)
73             {
74                 min=ans;
75             }
76         }
77         printf("%d
",min );
78     }
79 }