HDOJ1394 Minimum Inversion Number【线段树】

it2022-05-19  72

 

需要注意的就是给出的数是0~n-1,而线段树根节点范围是1-n

所以main中insert要num[i]+1、

当然,根节点范围换成0~n-1就不需要了。

Problem : 1394 ( Minimum Inversion Number )     Judge Status : AcceptedRunId : 5863168    Language : C    Author : qq1203456195

//往线段树中添加数据,每个结点记录的是 //当前结点范围已经插入的数字个数 //如果p点在左子树上,就累加右子树根节点上的记录 #include <stdio.h> #include <stdlib.h> #include <string.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 5001 int sum[maxn<<2],num[maxn+1]; int Min,s; void build() { memset(sum,0,sizeof(sum)); } void insert(int p,int l,int r,int rt) { int m; if(l<=p&&p<=r) sum[rt]++; if(l==r) return; m=((l+r)>>1); if(p<=m) { insert(p,lson); s+=sum[rt<<1|1]; } if(p>m) insert(p,rson); } int main() { int n,i; while (scanf("%d",&n)!=EOF) { //初始化 s=0; build(); //统计,得到s值 for (i=0;i<n;i++) { scanf("%d",&num[i]); insert(num[i]+1,1,n,1); } //求出Min Min=s; for (i=0;i<n;i++) { s=s-num[i]+n-1-num[i]; Min=Min<s?Min:s; } printf("%d\n",Min); } return 0; }

 

转载于:https://www.cnblogs.com/CheeseZH/archive/2012/04/28/2475573.html

相关资源:数据结构—成绩单生成器

最新回复(0)