洛谷P1249题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了洛谷P1249题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题引出

最大乘积

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 $3 = 1 + 2$ ， $4 = 1 + 3$ ， $5 ＝ 1 + 4 = 2 + 3$ ， $6 = 1 + 5 ＝ 2 + 4$ 。

现在你的任务是将指定的正整数 $n$ 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入格式

只一个正整数 $n$ ，（ $\leq n \leq 10000$ ）。

输出格式

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

样例 #1

样例输入 #1

样例输出 #1

2 3 5
30

二、思路分析

本题要先用简单的数论和贪心找到最优解的组成方法，再用高精度乘法求积。文章来源地址https://www.toymoban.com/news/detail-448178.html

以2004为例，由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种，因而一定存在一种分法,使得这些自然数的乘积最大。
若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多，乘积越大。为了使因数个数尽可能地多，我们把2004分成2+3…+n直到和大于等于2004。
若和比2004大1，则因数个数至少减少1个，为了使乘积最大,应去掉最小的2，并将最后一个数（最大）加上1。
两个特例，“3”和“4”。这两个只能从拆成“1+2”和“1+3”。

三、正确代码

#include <iostream>
using namespace std;
string add(string s,string t)
{
    int len1=s.length();
    int len2=t.length();
    if(len1<len2)
    {
        for(int i=0;i<(len2-len1);i++)
        {
            s="0"+s;
        }
    }
    else
    {
        for(int i=0;i<(len1-len2);i++)
        {
            t="0"+t;
        }
    }
    int len=s.length();
    int r=0;
    string result;
    for(int i=len-1;i>=0;i--)
    {
        int sum=(int(s[i]-'0')+int(t[i]-'0')+r)%10;
        r=(int(s[i]-'0')+int(t[i]-'0')+r)/10;
        result=char(sum+'0')+result;
    }
    if(r!=0)
        result=char(r+'0')+result;
    return result;
}
string mul(string s,string t)
{
    if (s=="0" || t=="0")
    {
        return "0";
    }  
    int len1=s.length();
    int len2=t.length();
    string result;
    for(int i=len2-1;i>=0;i--)
    {
        string midResult;
        //获取乘数的值方便待会进行运算
        int x=t[i]-'0';
        for(int j=0;j<x;j++)
        {
            midResult=add(midResult,s);
        }
        //移位操作
        for (int j = 0; j < len2-1-i; j++)
        {
            midResult+="0";
        }
        result=add(result,midResult);
    }
    return result;
}
/**
 * @brief 
 * ans数组用于保存加数
 * s数组用于保存对应加数的字符串
 */
int ans[1001];
string s[1001];
int main()
{
    int n,c=1;
    string result="1";
    cin>>n;
    if (n<=4)
    {
        cout<<"1 "<<n<<endl;
        cout<<n;
        return 0;
    }
    for (int i = 2; i <= n; i++)
    {
        if (n>=i)
        {
            n-=i;
            ans[c++]=i;
            s[c-1]=to_string(i);
        }
        else
        {
            break;
        }
    }
    for (int i = c-1; i >= 1; i--)
    {
        if (n>0)
        {
            ans[i]++;
            s[i]=to_string(ans[i]);
            n--;
        }
    }
    if (n>0)
    {
        ans[c-1]++;
        s[c-1]=to_string(ans[c-1]);
    }
    for (int i = 1; i <= c-1; i++)
    {
        cout<<ans[i]<<" ";
        result=mul(result,s[i]);
    }
    cout<<endl;
    cout<<result;
}