題意：

　　輸入一個長度 n

　　第二行給出長度為n的數組，數組的值剛好為0到n-1這n個數。

? ? ?然后每次把數組的第一個數放到最后一個，放n-1次，共有n個排列，這n個排列就有n個逆序數，輸出這n個逆序數的最小值。

我的做法：

1、每次輸入a[i]后，都把a[i] ++;

2、求出第一個排列的逆序數

3、遞推求出所有的逆序數

那怎么求1呢？

對于每一個a[i],求出1到i-1 中比它大的個數，然后相加，即可得。若用樸素的查找，肯定會超時的，所以這里就利用線段樹或者樹狀數組來快速查找。

線段樹版本：

?

1 #include<cstdio> 2 #include<cstring> 3 #define lson l,m,rt<<1 4 #define rson m+1,r,rt<<1|1 5 const int maxn=5010; 6 int c[maxn<<2]; 7 int a[maxn]; 8 int sum[maxn]; 9 void pushup(int rt) 10 { 11 c[rt]=c[rt<<1]+c[rt<<1|1]; 12 } 13 void update(int p,int add,int l,int r,int rt) 14 { 15 if(l==r){ 16 c[rt]+=add; 17 return; 18 } 19 int m=(l+r)>>1; 20 if(p<=m) 21 update(p,add,lson); 22 else 23 update(p,add,rson); 24 pushup(rt); 25 } 26 int query(int L,int R,int l,int r,int rt) 27 { 28 if(L<=l&&R>=r) 29 return c[rt]; 30 int m=(l+r)>>1; 31 int ret=0; 32 if(L<=m) 33 ret+=query(L,R,lson); 34 if(R>m) 35 ret+=query(L,R,rson); 36 return ret; 37 } 38 int main() 39 { 40 int n; 41 while(scanf("%d",&n)!=EOF){ 42 sum[1]=0; 43 memset(c,0,sizeof(c)); 44 for(int i=1;i<=n;i++){ 45 scanf("%d",&a[i]); 46 a[i]++; 47 sum[1]+=query(a[i],n,1,n,1); 48 update(a[i],1,1,n,1); 49 } 50 for(int i=2;i<=n;i++) 51 sum[i]=sum[i-1]+n+1-2*a[i-1]; 52 int ans=n*n; 53 for(int i=1;i<=n;i++) 54 if(sum[i]<ans) 55 ans=sum[i]; 56 printf("%d\n",ans); 57 } 58 return 0; 59 } View Code

?

用了46ms

?

?

樹狀數組版本：

1 #include<cstdio> 2 #include<cstring> 3 const int maxn=5010; 4 int c[maxn]; 5 int a[maxn]; 6 int sum[maxn]; 7 int lowbit(int x) 8 { 9 return x&(-x); 10 } 11 void update(int x,int d,int n) 12 { 13 while(x<=n){ 14 c[x]+=d; 15 x+=lowbit(x); 16 } 17 } 18 int query(int x) 19 { 20 int ret=0; 21 while(x>0){ 22 ret+=c[x]; 23 x-=lowbit(x); 24 } 25 return ret; 26 } 27 int main() 28 { 29 int n; 30 while(scanf("%d",&n)!=EOF){ 31 memset(c,0,sizeof(c)); 32 sum[1]=0; 33 for(int i=1;i<=n;i++){ 34 scanf("%d",&a[i]); 35 a[i]++; 36 sum[1]+=(i-1-query(a[i])); 37 update(a[i],1,n); 38 } 39 for(int i=2;i<=n;i++) 40 sum[i]=sum[i-1]+n+1-2*a[i-1]; 41 int ans=n*n; 42 for(int i=1;i<=n;i++) 43 if(ans>sum[i]) 44 ans=sum[i]; 45 printf("%d\n",ans); 46 } 47 return 0; 48 } View Code

也是46ms

?

轉載于:https://www.cnblogs.com/-maybe/p/4355340.html

總結

以上是生活随笔為你收集整理的hdu1394 Minimum Inversion Number 线段树和树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。