简单分解-最优分解贪心问题

简单分解-最优分解贪心问题

题目描述

现有一个数 ，需要把n分解成一个或多个两两互不相同的正整数（例如：可以分解成，也可以分解成，但不能分解成。当然也可以不分解，这样能分解的结果中累乘的最大值是），并累乘，累乘结果最大值可能是多少。

输入描述:

多组输入，每组一个正整数

输出描述:

输出一个整数，表示分解后累乘的最大值，结果对取模。

问题分析

首先，此类问题均属于最有分解问题。

我们首先关注整数的一个性质：若 (常数)，则越小， 越大

证明：，则有

则，显然越小，越大。

由于，那么我们需要对进行分类讨论：

1. 当时，的分解乘积小于，为获得极大的累乘结果，我们只能选择不分解
2. 当时，，因此至少从开始分解，可以保证乘积
3. 如果最后剩下的数字小于前一个，就要平均分配给前面的数字，且要从后往前分，反之可能会产生重复数字

将 分成从 开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。该贪心策略首先保证了正整数所分解出的因子之差的绝对值最小，即 最小；同时又可以将其分解成尽可能多的因子，且因子的值较大，确保最终所分解的自然数的乘积可以取得最大值 。

#include <bits/stdc++.h>
using namespace std;

#define Max 100005
int main(){
    int n; cin >> n;
    if (n < 4) return cout << n << endl, 0;
    int arr[Max] = {};
    int m = n, c = 2;
    int i;
    for (i = 0; c <= m; i++){
        arr[i] = c;
        m -= c;
        c++;
    }
    int cou = i; //一共有几个数
                 //如果优剩余的数 就从后往前平均分配到前的数字上
    while(m) arr[--i]++, m--;
    int mul = 1;
    for (int i = 0; i < cou; i++) mul *= arr[i];
    cout << mul << endl;
}