首页 > 代码库 > HDU 1394
HDU 1394
如果求出第一种情况的逆序列，其他的可以通过递推来搞出来，一开始是t[1],t[2],t[3]....t[N]
它的逆序列个数是sum个，如果把t[1]放到t[N]后面，逆序列个数会减少t[1]个，相应会增加N-(t[1]+1)个
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 #define N 5005 5 int sum[N*4],a[N]; 6 void build(int l,int r,int root){ 7 sum[root]=0; 8 if(l==r)return ; 9 int mid=(l+r)/2;10 build(l,mid,root*2);11 build(mid+1,r,root*2+1);12 }13 void update(int x,int l,int r,int root){14 if(l==r){15 sum[root]++;16 return;17 }18 int mid=(l+r)/2;19 if(x<=mid)update(x,l,mid,root*2);20 else update(x,mid+1,r,root*2+1);21 sum[root]=sum[root*2]+sum[root*2+1];22 }23 int query(int x,int y,int l,int r,int root){24 if(x<=l&&y>=r){25 return sum[root];26 }27 int add=0,mid=(r+l)/2;28 if(x<=mid)add+=query(x,y,l,mid,root*2);29 if(y>mid)add+=query(x,y,mid+1,r,root*2+1);30 return add;31 }32 int main(){33 freopen("test.txt","r",stdin);34 int t,s;35 while(scanf("%d",&t)!=EOF){36 build(0,t-1,1);37 s=0;38 for(int i=0;i<t;i++){39 scanf("%d",&a[i]);40 s+=query(a[i],t-1,0,t-1,1);41 update(a[i],0,t-1,1);42 }43 int ret=s;44 for(int i=0;i<t;i++){45 s+=t-a[i]-1-a[i];46 ret=min(ret,s);47 }48 printf("%d\n",ret);49 }50 return 0;51 }
#include <cstdio>
#include <iostream>
using namespace std;
#define N 5005
int sum[N*4],a[N];
void build(int l,int r,int root){
sum[root]=0;
if(l==r)return ;
int mid=(l+r)/2;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
}
void update(int x,int l,int r,int root){
if(l==r){
sum[root]++;
return;
}
int mid=(l+r)/2;
if(x<=mid)update(x,l,mid,root*2);
else update(x,mid+1,r,root*2+1);
sum[root]=sum[root*2]+sum[root*2+1];
}
int query(int x,int y,int l,int r,int root){
if(x<=l&&y>=r){
return sum[root];
}
int add=0,mid=(r+l)/2;
if(x<=mid)add+=query(x,y,l,mid,root*2);
if(y>mid)add+=query(x,y,mid+1,r,root*2+1);
return add;
}
int main(){
freopen("test.txt","r",stdin);
int t,s;
while(scanf("%d",&t)!=EOF){
build(0,t-1,1);
s=0;
for(int i=0;i<t;i++){
scanf("%d",&a[i]);
s+=query(a[i],t-1,0,t-1,1);
update(a[i],0,t-1,1);
}
int ret=s;
for(int i=0;i<t;i++){
s+=t-a[i]-1-a[i];
ret=min(ret,s);
}
printf("%d\n",ret);
}
return 0;
}