題目鏈接：[點擊打開鏈接](http://acm.hdu.edu.cn/showproblem.php?pid=1394) 對于求逆序數的問題， 通常用線段樹或者樹狀數組來維護， 樹狀數組代碼短，好寫， 還是盡量寫樹狀數組吧。 首先求出原始排列的逆序數， ?那么對于每一次操作， 因為都是將當前排列的第一個數拿到最后一個位置， 所以答案就增加了所有比他大的數字個數，減小了所有比他小的數字個數。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 5000+10; int T,n,m,bit[maxn],a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { while(~scanf("%d",&n)) { memset(bit, 0, sizeof(bit)); int ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]++; ans += sum(n) - sum(a[i]); add(a[i], 1); } int cur = ans; for(int i=1;i<n;i++) { int cnt = sum(a[i]-1); cur += n - 1 - cnt - cnt; ans = min(ans, cur); } printf("%d\n",ans); } return 0; } ~~~