题解 P1249 【最大乘积】

GCC_ · 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;
}