首页 > ACM题库 > HDU-杭电 > HDU 3473-Minimum Sum-高精度-[解题报告]HOJ
2014
04-04

HDU 3473-Minimum Sum-高精度-[解题报告]HOJ

Minimum Sum

问题描述 :

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!

输入:

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.

输出:

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.

样例输入:

2

5
3 6 2 2 4
2
1 4
0 2

2
7 7
2
0 1
1 1

样例输出:

Case #1:
6
4

Case #2:
0
0

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents          
by—cxlove

对于xl,xl+1……xr,使得[xi-x]和最小,显然x应当为其中的中位数。中位数可以通过求K大数解决,划分树可搞。

对于求和,分为两部分,小于x的部分,大于y的部分,在建树的时候也保存下来分到左子树中的数的和。

最终的和为ave*(lnum-rnum)+rsum-lsum

ave为中位数,lnum为左子数的数量,也就是小于中位数的数量,rnum为右子数,lsum表示小于中位数部分的和

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005
#define LL __int64
using namespace std;
struct Node{
	int left,right,mid;
}tree[N*4];
int sa[N],num[20][N],cnt[20][N]; //sa中是排序后的,num记录每一层的排序结果,cnt[deep][i]表示第deep层,前i个数中有多少个进入左子树
LL Lsum[20][N],sum[N];
int n,q;
void debug(int d){
	for(int i=1;i<=n;i++)
		printf("%d ",num[d][i]);
	printf("\n");
}
void bulid(int step,int l,int r,int deep){
	tree[step].left=l;
	tree[step].right=r;
	tree[step].mid=(l+r)>>1;
	if(l==r)
		return;
	int mid=(l+r)>>1;
	int mid_val=sa[mid],lsum=mid-l+1;;
	for(int i=l;i<=r;i++)
		if(num[deep][i]<mid_val)
			lsum--;    //lsum表示左子树中还需要多少个中值
	int L=l,R=mid+1;
	Lsum[deep][0]=0;
	for(int i=l;i<=r;i++){
		if(i==l)
			cnt[deep][i]=0;
		else
			cnt[deep][i]=cnt[deep][i-1];
		Lsum[deep][i]=Lsum[deep][i-1];
		if(num[deep][i]<mid_val||(num[deep][i]==mid_val&&lsum>0)){  //左子树
			num[deep+1][L++]=num[deep][i];
			cnt[deep][i]++;
			Lsum[deep][i]+=(LL)num[deep][i];
			if(num[deep][i]==mid_val)
				lsum--;
		}
		else
			num[deep+1][R++]=num[deep][i];
	}
//	debug(deep);
	bulid(2*step,l,mid,deep+1);
	bulid(2*step+1,mid+1,r,deep+1);
}
int lnum;
LL lsum;
int query(int step,int l,int r,int k,int deep){
	if(l==r)
		return num[deep][l];
	int s1,s2;   //s1为[tree[step].left,l-1]中分到左子树的个数
	if(tree[step].left==l)
		s1=0;
	else
		s1=cnt[deep][l-1];
	s2=cnt[deep][r]-s1;   //s2为[l,r]中分到左子树的个数
	if(k<=s2)   //左子树的数量大于k,递归左子树
		return query(2*step,tree[step].left+s1,tree[step].left+s1+s2-1,k,deep+1);
	int b1=l-1-tree[step].left+1-s1;  //b1为[tree[step].left,l-1]中分到右子树的个数
	int b2=r-l+1-s2;   //b2为[l,r]中分到右子树的个数
	lnum+=s2;
	lsum=(LL)lsum+Lsum[deep][r]-Lsum[deep][l-1];
	return query(2*step+1,tree[step].mid+1+b1,tree[step].mid+1+b1+b2-1,k-s2,deep+1);
}
int main(){
	int cas=0;
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n)	;
		sum[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&num[1][i]);
			sa[i]=num[1][i];
			sum[i]=(LL)sum[i-1]+sa[i];
		}
		sort(sa+1,sa+n+1);
		bulid(1,1,n,1);
		scanf("%d",&q);
		printf("Case #%d:\n",++cas);
		while(q--){
			int l,r,k;
			scanf("%d%d",&l,&r);
			l++;r++;
			k=(r-l+2)>>1;
			lnum=0;
			lsum=0;
			int ave=query(1,l,r,k,1);
			printf("%I64d\n",(LL)ave*(lnum-(r-l+1-lnum))+sum[r]-sum[l-1]-lsum-lsum);
		}
		puts("");
	}
	return 0;
}

参考:http://blog.csdn.net/acm_cxlove/article/details/7788305


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。