链接

[]

题意

有个数组，每次可以把第一个放到后面，然后求逆序数最小

所有数字都不同，而求是0~n-1

分析

树状数组求逆序数裸题

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define ll long longconst int N=1e4+10;int a[N],b[N];int n;int lowbit(int x){    return x&-x;}void update(int i,int va){    for(int j=i;j<=n;j+=lowbit(j))    a[j]+=va;}int gsum(int x){    int ans=0;    for(int i=x;i;i-=lowbit(i))    ans+=a[i];    return ans;}int main(){    //freopen("in.txt","r",stdin);    while(cin>>n){        memset(a,0,sizeof(a));        int sum=0;        for(int i=1;i<=n;i++){            cin>>b[i];            b[i]++;            update(b[i],1);            sum+=i-gsum(b[i]);        }        int mi=sum;        for(int i=1;i<=n;i++){            sum+=n-b[i]-(b[i]-1);            mi=min(mi,sum);        }        cout<
        
         <