题目大意
给定一个序列a1,a2,a3,..,an-1,an.每次通过把最左端的数转移到序列的最后面得到新的序列,通过n-1次操作,可以得到n-1个新的序列,要求你求出n个序列中逆序数最少的序列的逆序数总数
题解
可以用线段树求出原始序列的逆序数对总数sum来,然后通过通过递推可以求出另外n-1个序列的逆序对总数,用sum减去a[i](0<=i<=n-1)在转移之前右边比它小的数的总数(a[i])再加上转移之后a[i]左边比它大的数的总数(n-1-a[i]),那么得到的结果就是转移a[i]之后序列的逆序对总数
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #define lson l, m , s << 1 #define rson m + 1 , r , s << 1 | 1 #define MAXN 5005 #define INF 0x7ffffff using namespace std; int sumv[MAXN<<2]; int a[MAXN]; void PushUP(int s) { sumv[s]=sumv[s<<1]+sumv[s<<1|1]; } void build(int l,int r,int s) { sumv[s]=0; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } int query(int ql,int qr,int l,int r,int s) { if(ql<=l&&r<=qr) return sumv[s]; int m=(l+r)>>1; int ans=0; if(ql<=m) ans+=query(ql,qr,lson); if(m<r) ans+=query(ql,qr,rson); return ans; } void update(int p,int l,int r,int s) { if(l==r) { sumv[s]++; return; } int m=(l+r)>>1; if(p<=m) update(p,lson); else update(p,rson); PushUP(s); } int main(void) { int n; while(scanf("%d",&n)!=EOF) { int sum=0,mins=INF; build(0,n-1,1); for(int i=0; i<n; i++) { scanf("%d",&a[i]); sum+=query(a[i]+1,n-1,0,n-1,1); update(a[i],0,n-1,1); } for(int i=0; i<n; i++) { sum+=n-1-a[i]-a[i]; mins=min(mins,sum); } printf("%d\n",mins); } return 0; }