【基础练习】【贪心】codevs2612 最优分解方案题解

约定不等于承诺〃 2022-08-09 06:17 187阅读 0赞

题目描述 Description

为了迎接圣诞，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的主要内容是做游戏。经过第一轮的游戏，不少同学将会获得圣诞特别礼物，但这时细心的数学课代表发现了一个问题：留下来的人太多而使礼物数量可能不够，为此，加试了一道数学题：将一个正整数n分解成若干个互不相等的正整数的和，使得这些数的乘积最大，当主持人报出一个n后，请你立即将这个最大值报出来，现请你帮你的好友编一个程序来解决这个问题。

输入描述 Input Description

输入文件中只有1个数n（其中1<=n<=1000）。

输出描述 Output Description

输出文件中也是一个数，是乘积的最大值。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

需要高精才能AC

本题需要些高精，而且是高精乘单精。这意味着**一定要先集体乘完再集体进位，边乘边进位是会WA的！那是高精乘高精的做法！**

除此之外，基本的思想就是贪心了。当然也不要看错题，每个数字只能使用一次，这题不是乘积最大= =

所以方法应该是:

对于每个n ，将它分解为2~k的和以及一个多余的数值t，之后把t分在k-t+1 ~k 即这几个数加1

在网上找到了正确性的证明:

先对整数分解分析可以发现如下结论： 若 a + b = const，则 |a - b| 越小，a·b越大。   
根据原问题的描述，需要将正整数n分解为若干互不相同的自然数的和，同时又要使自然数的乘积最大。当n<4 时对n的分解的乘积是小于n的；当n大于或等于4时，n = 1 + (n-1)因子的乘积也是小于n的，所以n = a + (n-a), 2≤a≤n-2，可以保证乘积大于n，即越分解乘积越大。   
因此基于之前发现的结论和上面的分析，可以采用如下贪心策略：将n分成从2开始的连续自然数的和，如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。   
该贪心策略首先保证了正整数所分解出的因子之差的绝对值最小，即|a - b|最小；同时又可以将其分解成尽可能多的因子，且因子的值较大，确保最终所分解的自然数的乘积可以取得最大值。

那么上代码

//best
    //ÖØÐ´£¬Ò»¶¨ÒªÈÏÕæ¶ÁÌâ= =
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=200+10;
    const int power=5;
    const int base=10000;
    
    long long n,ans[200],a[200];
    
    inline void multi(long long *aa,long long b)//a=a*b
    {
        int lenb;
        if (b<10) lenb=1;
        else if (b<100) lenb=2;
        else if (b<1000) lenb=3;
        else lenb=4;
        for (int i=1;i<=aa[0];i++)
        {
            aa[i]=aa[i]*b;
        }
        while (aa[aa[0]+1]) aa[0]++;
        for (int i=1;i<=aa[0];i++)
        {
            aa[i+1]+=aa[i]/base;
            aa[i]%=base;
        }
        if (aa[aa[0]+1]) aa[0]++;
    }
    
    void print(long long *aa)
    {
        printf("%lld",aa[aa[0]]);
        for (long long i=aa[0]-1;i>=1;i--)
        {
            printf("%04lld",aa[i]);
        } 
        printf("\n");
        return;
    }
    
    int main()
    {
        freopen("best.in","r",stdin);
        freopen("best.out","w",stdout);
        scanf("%d",&n);
        if (n==8)
        {
            printf("15\n");
            return 0;
        }
        if (n<5)
        {
            if (n==1) printf("1\n");
            else if (n==2) printf("2\n");
            else if (n==3) printf("3\n");
            else if (n==4) printf("4\n");
            return 0;
        }
        int i=1;
        a[1]=2; 
        n-=2;
        while (n>=a[i]+1)
        {
            i++;
            a[i]=a[i-1]+1;
            n-=a[i];
        }
        int e=i;
        while (n--)//tryÕâÊ±ºò£¬ÏÈÖ´ÐÐ¸³ÖµÔÙ¼Ó¼õ£¬µ«ÎÞÂÛÊÇ·ñ·µ»Øture¶¼½øÐÐ¼Ó¼õ 
        {
            a[i--]++;
        }
        ans[0]=1;
        ans[1]=1;
        for (i=1;i<=e;i++)
        {
            multi(ans,a[i]);
        }
        print(ans);
        return 0;
    }

——独在异乡为异客，每逢佳节倍思亲