本文主要是介绍hdu1394，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：给出一个序列，每次讲队首放在队尾，求这个过程中逆序数最小是多少
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE=5005;
int segtree[SIZE<<2];
void build(int l,int r,int rt){
int m;
segtree[rt]=0;
if(l==r)
return ;
m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}
void update(int p,int add,int l,int r,int rt){
int m;
if(l==r){
segtree[rt]=add;
return ;
}
m=(l+r)>>1;
if(p<=m)
update(p,add,l,m,rt<<1);
else
update(p,add,m+1,r,rt<<1|1);
segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt){
int m,ans;
if(L<=l&&r<=R)
return segtree[rt];
m=(l+r)>>1;
ans=0;
if(L<=m)
ans+=query(L,R,l,m,rt<<1);
if(R>m)
ans+=query(L,R,m+1,r,rt<<1|1);
return ans;
} //线段树单点更新模板
int main(){ //这个题数据应该是不强，暴力找出逆序数
int n,i,j,ans,sum; //再递推出剩下的也可以
int x[5005];
while(scanf("%d",&n)!=EOF){
sum=0;
build(0,n-1,1); //建树嫌麻烦的话可以直接memmset
// memset(segtree,0,sizeof(segtree)); //反正刚开始整个树都是0
for(i=0;i<n;i++){
scanf("%d",&x[i]);
sum+=(i-query(0,x[i],0,n-1,1)); //用i减去前面输入的比当前x[i]小的就是这位的逆序数
update(x[i],1,0,n-1,1);
}
ans=sum;
for(i=0;i<n;i++){
sum=sum-x[i]+(n-1-x[i]); //减去原来产生的逆序数，再加上新产生的逆序数
ans=min(ans,sum);
}
printf("%d\n",ans);
}
return 0;
}
这篇关于hdu1394的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
