首页 > 代码库 > HDU 3473 Minimum Sum 划分树
HDU 3473 Minimum Sum 划分树
题目大意:给定一个序列,每次询问给出一个区间,我们需要选择一个数,这个数到区间内所有数的距离之和最小,求最小和
由绝对值不等式可得 当我们选择的这个数是中位数的时候距离和最小 于是这题就转换成了区间第k小
但是这题求的是最小和 于是我们做一个处理 我们多维护一个sum域 sum[i]表示[l,i]区间内划分到左子树中元素的总和
然后我们每次查询第k小时 如果我们进入的是右子树 就把划分到左子树中的元素和累加到left_sum上
然后用前缀和计算出区间的和 计算出right_sum
最后的结果就是k*mid_num-left_sum+right_sum-(y-x+1-k)*mid_num=right_sum-left_sum+(y-x-1-k-k)*mid_num
观察右式:
当区间长度为偶数时,y-x-1=2*k
当区间长度为奇数时,y-x-1=2*k-1
于是右式可化简为:
right_sum-left_sum+(y+x+1&1)*mid_num
此外很坑的一点就是和POJ不一样 HDU的C++和G++都是Windows评测 所以都要用%I64d输出 因为这个WA了半天 各种校对 真是蛋疼
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 100100 using namespace std; typedef long long ll; int n,m,cnt,a[M],b[M],c[M]; int s[20][M]; ll pre_sum[M],sum[20][M],left_sum,right_sum,ans; void Build_Tree(int l,int r,int dpt) { int i,mid=l+r>>1; int l1=l,l2=mid+1; int left=mid-l+1; if(l==r) return ; for(i=l;i<=r;i++) left-=(a[i]<c[mid]); for(i=l;i<=r;i++) { if(a[i]<c[mid]||a[i]==c[mid]&&left) { b[l1++]=a[i]; s[dpt][i]=(i==l?1:s[dpt][i-1]+1); sum[dpt][i]=(i==l?a[i]:sum[dpt][i-1]+a[i]); left-=(a[i]==c[mid]); } else { b[l2++]=a[i]; s[dpt][i]=(i==l?0:s[dpt][i-1]); sum[dpt][i]=(i==l?0:sum[dpt][i-1]); } } memcpy( a+l , b+l , sizeof(a[0])*(r-l+1) ); Build_Tree(l,mid,dpt+1); Build_Tree(mid+1,r,dpt+1); } int Get_Ans(int l,int r,int dpt,int x,int y,int k) { int i,mid=l+r>>1; int l1=(x==l?0:s[dpt][x-1]),l2=s[dpt][y]; if(l==r) { left_sum+=a[mid]; return a[mid]; } if(k<=l2-l1) return Get_Ans(l,mid,dpt+1,l+l1,l+l2-1,k); else { left_sum+=sum[dpt][y]-(x==l?0:sum[dpt][x-1]); return Get_Ans(mid+1,r,dpt+1,(mid+1)+(x-l-l1),(mid+1)+(y-l+1-l2)-1,k-l2+l1); } } int main() { //freopen("1.txt","w",stdout); int T,i,x,y,k; for(cin>>T;T;T--) { printf("Case #%d:\n",++cnt); cin>>n; for(i=1;i<=n;i++) scanf("%d",&a[i]),c[i]=a[i],pre_sum[i]=pre_sum[i-1]+a[i]; sort(c+1,c+n+1); Build_Tree(1,n,0); cin>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); x++;y++;k=y-x+2>>1;left_sum=0; ll mid_num=Get_Ans(1,n,0,x,y,k); right_sum=pre_sum[y]-pre_sum[x-1]-left_sum; ans=right_sum-left_sum+(x+y+1&1)*mid_num; //ans=k*mid_num-left_sum+right_sum-(y-x+1-k)*mid_num; printf("%I64d\n",ans); } putchar('\n'); } }
HDU 3473 Minimum Sum 划分树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。