HDU 5312：Sequence

Sequence

Accepts: 25

Submissions: 1442

Time Limit: 2000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

问题描述

Soda习得了一个数列, 数列的第 $n$   $(n \geq 1)$ 项是 $3 n (n - 1) + 1$ . 现在他想知道对于一个给定的整数 $m$ , 是否可以表示成若干项上述数列的和. 如果可以, 那么需要的最小项数是多少?

例如, 22可以表示为 $7 + 7 + 7 + 1$ , 也可以表示为 $19 + 1 + 1 + 1$ .

输入描述

输入有多组数据. 第一行有一个整数 $T$   $10^4)$ , 表示测试数据组数. 然后对于每组数据:

一行包含1个整数  $m$   $10^9)$ .

输出描述

对于每组数据输出最小花费.

输入样例

输出样例

题解：

这个题看上去是一个贪心, 但是这个贪心显然是错的. 事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的 $k (k > 2)$ , 使得 $(m - k) m o d 6 = 0$ 即可.

证明如下: $3 n (n - 1) + 1 = 6 (n * (n - 1) / 2) + 1$ , 注意到 $n * (n - 1) / 2$ 是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要 $k$ 个, 那么显然 $m = 6 (k$ 个三角形数的和 $) + k$ , 由于 $k \geq 3$ , 只要 $m - k$ 是6的倍数就一定是有解的.

事实上, 打个表应该也能发现规律.

做的时候就想这题贪心肯定是WA，但最后还是稀里糊涂地贪心了。推的时候还在想n∗(n−1)/2这个式子应该有什么性质，但真不知道这个是三角形数，并且任意一个自然数最多只需要3个三角形数

就能表示了，也是通过这个题涨了姿势吧。

有了这个解题思路之后，以为程序就变得很好写了，结果在找两个的时候，写了两层循环，愤怒的TLE啊。。。

找两个的时候这段代码，又一次被教做人了：

		while(i<=j)
		{
			if(sum_2[i]+sum_2[j] == cal)
				return 2;
			else if(sum_2[i]+sum_2[j]<cal)
				i++;
			else 
				j--;
		}

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

int cal,i,j,temp1,temp2,sum;//18528
int sum_2[20000];

int solve()
{
	if(cal%6==1)
	{
		for(i=1;i<18528;i++)
		{
			if(sum_2[i]<cal)continue;
			if(sum_2[i]>cal)
				break;
			else if(sum_2[i]==cal)
				return 1;
		}
		return 7;
	}
	else if(cal%6==2)
	{
		i=1;j=18527;
		while(i<=j)
		{
			if(sum_2[i]+sum_2[j] == cal)
				return 2;
			else if(sum_2[i]+sum_2[j]<cal)
				i++;
			else 
				j--;
		}
		return 8;
	}
	else if(cal%6==0)
		return 6;

	return cal%6;

}
int main()
{	
	for(i=1;i<18528;i++)
	{
		sum_2[i]=3*i*(i-1)+1;
	}
	int Test1;
	scanf("%d",&Test1);

	while(Test1--)
	{
		scanf("%d",&cal);
		printf("%d
",solve());
	}
	return 0;
}

发现这个世界真是辽阔，每一次都能学到之前自己并不知道的，更加优化的算法。每一次都被虐得很抱怨，但每一次也都有很多收获。