乘积最大3

GitHub跳转原题关系图返回列表

把 N 尽量平均拆成 M 份，商和余数直接决定最优方案。

OJ: luogu

题目 ID: P1887

难度:普及-

标签:数学贪心

日期: 2026-06-18 20:42

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

把整数 N 拆成 M 个正整数，要求它们的和等于 N，并且乘积尽可能大。 如果有多种最优方案，输出字典序最小的一种。

思路

先看一个可以直接验证想法的朴素解：

小数据时可以枚举所有非降序拆分方案，计算乘积并选最优。

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

long long n, m;
vector<long long> cur, best;
long long best_product = -1;

void dfs(int idx, long long last, long long left_sum, long long product) {
    if (idx == m) {
        if (left_sum != 0) return;
        if (product > best_product || (product == best_product && cur < best)) {
            best_product = product;
            best = cur;
        }
        return;
    }

    long long remain = m - idx;
    for (long long x = last; x <= left_sum / remain; x++) {
        cur.push_back(x);
        dfs(idx + 1, x, left_sum - x, product * x);
        cur.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    dfs(0, 1, n, 1);

    for (int i = 0; i < (int) best.size(); i++) {
        if (i) cout << ' ';
        cout << best[i];
    }
    cout << '\n';

    return 0;
}

关键结论是：如果两个数相差至少 2，那么把大的减 1、小的加 1，总和不变，但乘积会更大。 所以最优方案一定是“尽量平均分”的。

设：

text
N = M * q + r

那么答案就是：

  • M - r 个 q
  • r 个 q + 1

把小的放前面，也正好满足字典序最小。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m;
    cin >> n >> m;

    long long base = n / m;
    long long extra = n % m;

    bool first = true;
    for (long long i = 0; i < m - extra; i++) {
        if (!first) cout << ' ';
        cout << base;
        first = false;
    }
    for (long long i = 0; i < extra; i++) {
        if (!first) cout << ' ';
        cout << base + 1;
        first = false;
    }
    cout << '\n';

    return 0;
}

复杂度

只需要输出 M 个数，所以时间复杂度是 O(M)O(M)，空间复杂度是 O(1)O(1)。

总结

这题的关键不是搜索，而是发现“总和固定时，数越平均乘积越大”。