自动搬运

查看原文

来自洛谷，原作者为

	GCC_ 暴力打满得天下，花式水法能AC。若有一题不可做，骗分打表总能行

搬运于2025-08-24 21:22:55，当前版本为作者最后更新于2019-04-05 20:20:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

2023.12.12 更新

二次修改完成。你谷数据该加强了。

经过本人思考验证，之前的一处思路出现了问题（当时是照着评论区改的，没有验证正确性）。现在已更正。

2023.7.17 更新

感谢评论区指出的错误，很抱歉对大家造成了误解。

题目简述

让你将一个正整数 $n$ 分解成若干个自然数之和，要求这些数的乘积最大。

做题步骤

1. 观察性质；
2. 得出结论；
3. 完善代码。

观察性质

先举出几个简单的例子：

• $5\rightarrow2\times 3$
• $6\rightarrow2\times 4$
• $9\rightarrow2\times 3\times 4$
• $10\rightarrow2\times 3\times 5$

我们观察到，大部分分解出来的数都是较为连续的。

得出结论

考虑这样一种贪心策略：

首先构造出连续一段自然数，使得和恰好大于或等于 $n$ ，然后找到一个合适的数并更改（如果等于 $n$ 就不更改），使得和满足要求。

例如分解一个数 $15$ ：

• 首先找到连续一段自然数： $2+3+4+5+6>15$ （为什么要从 $2$ 开始而不是 $3$ 或更大？请思考）；
• 发现 $2+3+4+5+6=20$ ，恰好与 $15$ 相差 $5$ ；
• 把 $5$ 删掉，得到 $2+3+4+6=15$ ，计算答案。

若找到的和与 $n$ 相差 $1$ ，可以直接删除 $2$ 并将最后一个数加上 $1$ 。

注意：当 $n=3,4$ 时并不符合上述的贪心策略，需要特判。

完善代码

#include<iostream>
using namespace std;
int a[10001]={};
int s[10001]={};
int n,len=1;
void mul(int x)
{
	for(int i=1;i<=len;i++)s[i]*=x;
	for(int i=1;i<=len;i++)
	{
		s[i+1]+=s[i]/10;
		s[i]%=10;
	}
	while(s[len+1]>0)
	{
		len++;
		s[len+1]+=s[len]/10;
		s[len]%=10;
	}
}
int main()
{
	cin>>n;
	if(n==3)
	{
		cout<<3<<endl;
		cout<<3<<endl;
		return 0;
	}
	if(n==4)
	{
		cout<<4<<endl;
		cout<<4<<endl;
		return 0;
	}
	s[0]=s[1]=1;
	int Sum=0,tot=0;
	for(int i=2;Sum<n;Sum+=i,i++)a[++tot]=i;
	if(Sum>n+1)a[Sum-n-1]=0;
	else if(Sum==n+1)a[tot]++,a[1]=0;
	for(int i=1;i<=tot;i++)
	{
		if(a[i])
		{
			cout<<a[i]<<' ';
			mul(a[i]);
		}
	}
	cout<<endl;
	for(int i=len;i>=1;i--)
		cout<<s[i];
	cout<<endl;
	return 0;
}