題目:Minimum Inversion Number

鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1394

分析:

1）先對序列求逆序對的數目，歸并排序，線段樹，樹狀數組都可以。

2）考慮到這是一個[0,n)的排列，全體加一，變成一個[1,n]的排列。

3）把第一個數移動到最后一位對答案的貢獻是(n-a[1])-(a[1]-1)。在第二位到最后一位比a[1]大的有（n-a[1]），這些將由順序變逆序，比a[1]小的有（a[1]-1），這些將由逆序變順序。

4）這是一個環，i從頭枚舉，第i位成為首位，移動到末尾時，對答案的貢獻是(n-a[i])-(a[i]-1)。

5）取個最小值即可。

#include <bits/stdc++.h> using namespace std; const int maxN=50005; int n,a[maxN],T[maxN]; void Tadd(int x,int y){for(int i=x;i<=n;i+=i&-i)T[i]+=y;} int Tque(int x){int ret=0;for(int i=x;i;i-=i&-i)ret+=T[i];return ret;} int main(){for(int ans,tans;~scanf("%d",&n);){tans=0;for(int i=1;i<=n;++i)T[i]=0;for(int i=1;i<=n;++i){scanf("%d",&a[i]);++a[i];}for(int i=n;i>=1;--i){tans+=Tque(a[i]);Tadd(a[i],1);}ans=tans;for(int i=1;i<=n;++i){tans+=n-a[i]-a[i]+1;ans=min(ans,tans);}printf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/hjj1871984569/p/10347201.html

總結

以上是生活随笔為你收集整理的[HDU1394]Minimum Inversion Number的全部內容，希望文章能夠幫你解決所遇到的問題。

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