HDU-1394

给定一个由 $0$ 到 $n−1$ 组成，长度为 $n$ 每个元素唯一的序列，可以进行一种操作，把第一个元素放到最后一个位置。求经过若干次操作后的，最小逆序对数。

思路

我习惯 $1$ 到 $n$ ，于是先转换为 $1$ 到 $n$ ，将所有元素都加 $1$ 。

只需考虑将第一个元素放到最后一个位置对逆序对数的影响。

假设第一个元素为 $t$ ，将该元素删去，总逆序对数应减少其后面比 $t$ 小的数的数量，由为 $1$ 到 $n$ 排列，所以即为 $t-1$ 。

再将最后一个元素加入到末尾，那么总逆序对数增加其前面比 $t$ 大的数的数量，由为 $1$ 到 $n$ 的排列，所以即为 $n-t$ 。

如此即可。

代码

求逆序对我用的是线段树。

#include<bits/stdc++.h>
#define N 5010
#define INF 0x7fffffff

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

class SegmentTree{
  private:
    int sum[N<<2];
    #define s(x) sum[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            s(p)=0;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int x) {
        if(l>x||r<x) return ;
        if(l==r) {
            s(p)=1;
            return ;
        }
        modify(ls,l,mid,x),modify(rs,mid+1,r,x);
        update(p);
    }
    int ask(int p,int l,int r,int x) {
        if(r<x) return 0;
        if(l>=x) return s(p);
        return ask(ls,l,mid,x)+ask(rs,mid+1,r,x);
    }
}SMT;

int n,a[N],sum,minn;

void init() {
    sum=0,minn=INF;
    SMT.build(1,1,n);
}

int main() {
    while(cin>>n) {
        for(int i=1;i<=n;i++) a[i]=read()+1;
        init();
        for(int i=1;i<=n;i++) {
            sum+=SMT.ask(1,1,n,a[i]);
            SMT.modify(1,1,n,a[i]);
        }
        minn=sum;
        for(int i=1;i<=n;i++) {
            sum-=a[i]-1;
            sum+=n-a[i];
            minn=min(sum,minn);
        }
        printf("%d\n",minn);
    }
    return 0;
}