首页 > ACM题库 > HDU-杭电 > HDU 3280-Equal Sum Partitions-分治-[解题报告]HOJ
2014
03-13

HDU 3280-Equal Sum Partitions-分治-[解题报告]HOJ

Equal Sum Partitions

问题描述 :

An equal sum partition of a sequence of numbers is a grouping of the numbers (in the same order as the original sequence) in such a way that each group has the same sum. For example, the sequence:
2 5 1 3 3 7
may be grouped as:
(2 5) (1 3 3) (7)
to yield an equal sum of 7.

Note: The partition that puts all the numbers in a single group is an equal sum partition with the sum equal to the sum of all the numbers in the sequence.

For this problem, you will write a program that takes as input a sequence of positive integers and returns the smallest sum for an equal sum partition of the sequence.

输入:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer M, (1 ≤ M ≤ 10000), giving the total number of integers in the sequence. The remaining line(s) in the dataset consist of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.

输出:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer M, (1 ≤ M ≤ 10000), giving the total number of integers in the sequence. The remaining line(s) in the dataset consist of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.

样例输入:

3
1 6
2 5 1 3 3 7
2 6
1 2 3 4 5 6
3 20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

样例输出:

1 7
2 21
3 2

/*
分析:
    用了线段树+二分搜索,树状数组+二分搜索也行。

                                       2012-10-03
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
struct seg
{
	__int64 l,r,mid;
	__int64 sum;
}T[30333];
__int64 set[10011];

void build(__int64 l,__int64 r,__int64 k)
{
	T[k].l=l;
	T[k].r=r;
	T[k].mid=(l+r)>>1;


	if(l==r)	{T[k].sum=set[l];return ;}


	build(l,T[k].mid,2*k);
	build(T[k].mid+1,r,2*k+1);
	T[k].sum=T[2*k].sum+T[2*k+1].sum;
}

__int64 find(__int64 l,__int64 r,__int64 k)
{
	__int64 ans_t=0;

	if(T[k].l==l && T[k].r==r)	return T[k].sum;
	
	if(r<=T[k].mid)		ans_t+=find(l,r,2*k);
	else if(l>T[k].mid)	ans_t+=find(l,r,2*k+1);
	else
	{
		ans_t+=find(l,T[k].mid,2*k);
		ans_t+=find(T[k].mid+1,r,2*k+1);
	}
	return ans_t;
}

__int64 main()
{
	__int64 T,Case;
	__int64 n;
	__int64 i;
	__int64 left,up,mid,low;
	__int64 count;
	__int64 sum,base;
	__int64 ans,ans_t;
	scanf("%I64d",&T);
	for(Case=1;Case<=T;Case++)
	{
		scanf("%I64d%I64d",&n,&n);
		sum=0;
		for(i=1;i<=n;i++)	{scanf("%I64d",&set[i]);sum+=set[i];}
		build(1,n,1);

		ans=0;
		for(i=sum;i>1;i--)
		{
			if(ans)	break;
			if(sum%i==0)
			{
				base=sum/i;
				count=0;
				left=1;
				while(count<i)
				{
					up=left;
					low=n;
					mid=(up+low)>>1;
					while(up<=low)
					{
						ans_t=find(left,mid,1);
						if(ans_t==base)	break;
						if(ans_t>base)	low=mid-1;
						else			up=mid+1;
						mid=(low+up)>>1;
					}
					if(ans_t==base)
					{
						count++;
						left=mid+1;
					}
					else	break;
				}
				if(count==i)	ans=base;
			}
		}
		if(ans==0)	ans=sum;

		printf("%I64d %I64d\n",Case,ans);
	}
	return 0;
}

参考:http://blog.csdn.net/ice_crazy/article/details/8037666


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。