題目大意：
給由0-n-1這n個數構成的n個數，定義一個逆序數（前面的比後面的大的數的個數）。把第一個數移到最後的位置，得到一個新的序列，得到一個新的逆序數。一共可以移動n-1次，得到n個逆序數，問這n個逆序數最小的是多少。
解題思路：
1、先求出第一個序列的逆序數。
根據題目特點，建立一個0——(n-1)的線段樹，每個區間保存含有當前區間內數的個數。
對每一個數，查找該數到n-1內已存在數的個數，（因為該數前面的所有數都壓到線段樹裡面去了），再把該數壓進去。
把每個數前面的逆序數加起來，就可以構造出整個逆序數。
2、當把第一個移到最後時，後面有0——(save[1]-1)一共save[1]個數比save[i]小，共有n-1-save[1]個數比save[1]大
所以得到遞推公式，sum=sum-save[i]+(n-1-save[i])。
代碼：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
#define maxn 5100
int sum[4*maxn],save[maxn];
void build(int l,int r,int rt)
{
sum[rt]=0; //表示該區間一共有多少個數
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
return ;
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r) //如果要找區間大於當前區間，直接返回當前區間
return sum[rt];
int m=(l+r)>>1,temp=0;
if(R<=m)
return query(L,R,lson);
else if(L>m)
return query(L,R,rson);
else
{
temp+=query(L,R,lson);
temp+=query(L,R,rson);
return temp;
}
}
void pushup(int rt) //向上更新，每次插入的時候向上更新，注意是覆蓋
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int target,int l,int r,int rt)
{
if(l==r)
{
sum[rt]++;
return ;
}
int m=(l+r)>>1;
if(target<=m)
update(target,lson);
else
update(target,rson);
pushup(rt);
return ;
}
int main()
{
int n,temp;
while(scanf("%d",&n)!=EOF)
{
int sum=0;
build(0,n-1,1); //注意區間是0-(n-1)
for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
sum+=query(save[i],n-1,0,n-1,1);
update(save[i],0,n-1,1);
}
int ans=sum;
for(int i=1;i<n;i++)
{
sum+=n-2*save[i]-1;
ans=min(sum,ans);
}
printf("%d\n",ans);
}
return 0;
}
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
#define maxn 5100
int sum[4*maxn],save[maxn];
void build(int l,int r,int rt)
{
sum[rt]=0; //表示該區間一共有多少個數
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
return ;
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r) //如果要找區間大於當前區間，直接返回當前區間
return sum[rt];
int m=(l+r)>>1,temp=0;
if(R<=m)
return query(L,R,lson);
else if(L>m)
return query(L,R,rson);
else
{
temp+=query(L,R,lson);
temp+=query(L,R,rson);
return temp;
}
}
void pushup(int rt) //向上更新，每次插入的時候向上更新，注意是覆蓋
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int target,int l,int r,int rt)
{
if(l==r)
{
sum[rt]++;
return ;
}
int m=(l+r)>>1;
if(target<=m)
update(target,lson);
else
update(target,rson);
pushup(rt);
return ;
}
int main()
{
int n,temp;
while(scanf("%d",&n)!=EOF)
{
int sum=0;
build(0,n-1,1); //注意區間是0-(n-1)
for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
sum+=query(save[i],n-1,0,n-1,1);
update(save[i],0,n-1,1);
}
int ans=sum;
for(int i=1;i<n;i++)
{
sum+=n-2*save[i]-1;
ans=min(sum,ans);
}
printf("%d\n",ans);
}
return 0;
}
