hdu 1394 Minimum Inversion Number（线段树单点更新）

hdu 1394 Minimum Inversion Number（线段树单点更新）

题意：给定一个数字序列，如果一次次的把左边第一个数移动到最右边，它的逆序数将会发生变化，问：找出最小的逆序数。题意详见：​​所以可以在叶子节点上存储各个改变量，而在各父节点上存储最小的改变量。最终根节点的对应值就是相对原始序列最小的逆序数的最小改变量。

接下来写上代码即可：

#include #includeusing namespace std;const int maxn=5e3+5;int num[maxn];struct node{ int left,right,sum;}btree[3*maxn]; void build(int root,int l,int r){ btree[root].left=l; btree[root].right=r; if(l==r){ btree[root].sum=0; return ; } int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); btree[root].sum=min(btree[2*root].sum,btree[2*root+1].sum); //递归回溯赋值给双亲结点}void update(int root,int pos,int val){ if(btree[root].left==btree[root].right){ btree[root].sum=val; return ; } int mid=(btree[root].left+btree[root].right)/2; if(pos<=mid)update(2*root,pos,val); else update(2*root+1,pos,val); btree[root].sum=min(btree[2*root].sum,btree[2*root+1].sum);}int main(){ //freopen("cin.txt","r",stdin); int n,i,j; while(cin>>n){ int res=0; build(1,1,n); for(i=1;i<=n;i++){ scanf("%d",&num[i]); res+=n-1-2*num[i]; update(1,num[i],res); } res=0; for(i=1;inum[j])res++; } } printf("%d\n",btree[1].sum+res); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。