这题就是给你一个数列，然后依次把开头的数移到最后，一直到又恢复原状，输出这些变化中最小的逆序数，我是先求出了最初的逆序数，然后后面可以用公式直接枚举出
#include <iostream> #include <cstring> using namespace std; #define MAX 30000 #define MAX_S 5001 // hdu 1394 typedef struct node { int s,e; int w; //int val; node (int a=0,int b=0,int c=0):s(a),e(b),w(c){} }node; int arr[MAX_S]; node tree[MAX]; int flag=0; //在这里是 用 【4,6】这样的线段表示，4,5,6，那么如果输入3，我们查找时就到 3+1开始的区间， void build (int T,int s,int e) //该区间就表示了比三大的数目有多少 { if (s == e) { tree[T] = node (s,e,0); } else { int mid = (s+e)>>1; build (T<<1,s,mid); build (T<<1|1,mid+1,e); tree[T] = node(s,e,0); } } //查找大于a[i]的元素，在【a[i]+1,n-1】区间中，查找，因为，如果前面输入的数有大于a[i] int Query(int T,int s,int e)//的，那么一定会被更新到对应的区间，所以你在 [a[i]+1,n-1] { //区间查找，便一定能找到对应的逆序数个数 if (s <= tree[T].s && tree[T].e <=e) return tree[T].w; int mid = (tree[T].s+tree[T].e)>>1; int s1 =0,s2=0; if (s<=mid) s1 = Query(T<<1,s,e); if (e>mid) s2 = Query(T<<1|1,s,e); return s1+s2; } //一直递归直到找到 e 号节点，使该节点的W值为1，于是下一次查询时，如果是小于e的数 void update (int T,int e) //那么一定会找到e 号节点，从而逆序数加一 { if (tree[T].s == e && tree[T].e == e) { tree[T].w=1; return ; } int mid = (tree[T].s+tree[T].e)>>1; if (e<=mid) update(T<<1,e); else update(T<<1|1,e); tree[T].w = tree[T<<1].w+tree[T<<1|1].w; } int main () { std::ios::sync_with_stdio(false); int n; while(cin>>n) { build(1,0,n-1); int ans = 0; for (int i=0;i<n;++i) { cin>>arr[i]; ans +=Query(1,arr[i]+1,n-1); update(1,arr[i]); } int min = ans; //公式 for (int i=0;i<n;++i) { ans = ans +n-1-2*arr[i]; if (min > ans) min =ans; } cout<<min<<endl; } return 0; } /* 10 1 3 6 9 0 8 5 7 4 2 */