首页 > 代码库 > HDU 3473 Minimum Sum
HDU 3473 Minimum Sum
Minimum Sum
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2667 Accepted Submission(s): 609
Problem Description
You are given N positive integers, denoted as x0, x1 ... xN-1. Then give you some intervals [l, r]. For each interval, you need to find a number x to make as small as possible!
Input
The first line is an integer T (T <= 10), indicating the number of test cases. For each test case, an integer N (1 <= N <= 100,000) comes first. Then comes N positive integers x (1 <= x <= 1,000, 000,000) in the next line. Finally, comes an integer Q (1 <= Q <= 100,000), indicting there are Q queries. Each query consists of two integers l, r (0 <= l <= r < N), meaning the interval you should deal with.
Output
For the k-th test case, first output “Case #k:” in a separate line. Then output Q lines, each line is the minimum value of . Output a blank line after every test case.
Sample Input
2 5 3 6 2 2 4 2 1 4 0 2 2 7 7 2 0 1 1 1
Sample Output
Case #1: 6 4 Case #2: 0 0
Author
standy
Source
2010 ACM-ICPC Multi-University Training Contest(4)——Host by UESTC
解题思路:显然x是中位数,用划分树找出来,用lsum[20][i]维护每一层从1到i划分到左子树的数的和,查询区间的时候找到区间内划分到左子树的数的个数lnum和他们的和suml,最后公式是mid*lnum-suml+mid*rnum-sumr。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define LL long long using namespace std; const int Maxn=100010; int tree[20][Maxn]; LL lsum[20][Maxn],suml; int sorted[Maxn]; int toleft[20][Maxn]; LL sum[Maxn]; int lnum; void build(int l,int r,int dep) { if(l==r) return ; int mid=(l+r)>>1; int same=mid-l+1; for(int i=l;i<=r;i++) { if(tree[dep][i]<sorted[mid]) same--; } int lpos=l; int rpos=mid+1; for(int i=l;i<=r;i++) { if(tree[dep][i]<sorted[mid]) { tree[dep+1][lpos++]=tree[dep][i]; lsum[dep][i]=lsum[dep][i-1]+tree[dep][i]; } else if(tree[dep][i]==sorted[mid]&&same>0) { tree[dep+1][lpos++]=tree[dep][i],same--; lsum[dep][i]=lsum[dep][i-1]+tree[dep][i]; } else { tree[dep+1][rpos++]=tree[dep][i]; lsum[dep][i]=lsum[dep][i-1]; } toleft[dep][i]=toleft[dep][l-1]+lpos-l; } build(l,mid,dep+1); build(mid+1,r,dep+1); } int query(int L,int R,int l,int r,int dep,int k) { if(l==r) return tree[dep][l]; int mid=(L+R)>>1; int cnt=toleft[dep][r]-toleft[dep][l-1]; if(cnt>=k) { int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else { lnum+=cnt; suml+=lsum[dep][r]-lsum[dep][l-1]; int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } int main() { int t,n,m,q,a,b,ncase=1; freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); scanf("%d",&t); while(t--) { scanf("%d",&n); memset(tree,0,sizeof(tree)); sum[0]=0; for(int i=1;i<=n;i++) scanf("%d",&tree[0][i]),sorted[i]=tree[0][i],sum[i]=sum[i-1]+sorted[i]; sort(sorted+1,sorted+1+n); build(1,n,0); scanf("%d",&m); printf("Case #%d:\n",ncase++); while(m--) { scanf("%d%d",&a,&b); a++,b++; int k=(b-a)/2+1; lnum=suml=0; //suml是所有中位数左边的数的和 int tmp=query(1,n,a,b,0,k); int rnum=b-a+1-lnum; LL sumr=sum[b]-sum[a-1]-suml;//sumr是所有中位数开始的右边的数的和(包括中位数) LL ans=sumr-tmp*rnum+tmp*lnum-suml; printf("%I64d\n",ans); } printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。