首页 > ACM题库 > HDU-杭电 > HDU 1725 Find minimal sum[解题报告]
2013
12-21

HDU 1725 Find minimal sum[解题报告]

Find minimal sum

问题描述 :

每一个正整数都可以表示成m = An-1(n-1)! + An-2(n-2)! + An-3(n-3)! + … + A1, (0<=Ai<=i, j =1, 2, …, n-1)的形式. 但是对于一个给定的正整数, ACboy的老师要他找出最小的min(An-1 + An-2 + .. + A1)满足m = An-1(n-1)! + An-2(n-2)! + An-3(n-3)! + … + A1.
你能帮帮他吗?

输入:

输入首先给出一个N, 代表有N个测试实例。
接下来的N行, 每行包括一个正整数M (1 <= M < 2^32).

输出:

对于每个测试实例输出min(An-1 + An-2 + .. + A1).

样例输入:

3
2
3
100

样例输出:

1
2
6
Hint

对于2, 可以写成3 = 1*2!, 所以答案为1. 对于3, 可以写成3 = 1*2! + 1*1!, 所以答案为2. 对于100, 可以写成100 = 4*4! + 2*2!, 所以答案为6.

http://acm.hdu.edu.cn/showproblem.php?pid=1725

 

一道水题,磨蹭了半天,我的代码(ac):

#include<stdio.h>

int getN(int n)
{
	int f=1;
	for(int i=1;i<=n;i++)
       f*=i;
	return f;
}

int get(int m)//返回值的阶乘为小于m的最大值
{
	int i,f;
	for(i=1;i<=m;i++)
	{
       f=getN(i);
	   if(f==m)
		   return i;
	   if(f>m)
		   	break;
	}
	return i-1;
}

int main()
{
	int n,m,i,j,min,t,k;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		min=0;
        scanf("%d",&m);
		while(m>0)
		{
		   k=get(m);
           for(j=k;j>=0;j--)
		   {
			   t=j*getN(k);
               if(t<=m)
			   {
				   min+=j;
				   m-=t;
				   break;
			   }
		   }
		}
		printf("%d/n",min);
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/enjoyinwind/article/details/6272632