乘积最大 3 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求把正整数 $N$ ~N~ 拆成 $M$ ~M~ 个正整数之和，在乘积尽可能大的前提下输出字典序最小的方案。核心解法是均值原理：最优方案中任意两数之差不超过 $1$ ~1~，即所有元素只取 $\lfloor N/M \rfloor$ ~\lfloor N/M \rfloor~ 与 $\lceil N/M \rceil$ ~\lceil N/M \rceil~ 两种值，各自的个数由总和唯一确定，按非降序排列即为字典序最小的方案。

分析

核心观察

若方案中存在两数之差大于等于 $2$ ~2~，把较大的数减 $1$ ~1~、较小的数加 $1$ ~1~，总和不变而乘积严格变大。因此乘积最大的方案中任意两数之差不超过 $1$ ~1~，所有数都紧贴平均值。

思路

设方案为 $a_1, a_2, \dots, a_M$ ~a_1, a_2, \dots, a_M~，其和为 $N$ ~N~。若存在两个元素满足 $a_i \le a_j - 2$ ~a_i \le a_j - 2~，把它们替换为 $a_i + 1$ ~a_i + 1~ 与 $a_j - 1$ ~a_j - 1~，总和保持不变，而乘积的变化量为

$\displaystyle (a_i + 1)(a_j - 1) - a_i a_j = a_j - a_i - 1 > 0$

乘积严格增大，与方案的最优性矛盾。故最优方案中任意两数之差不超过 $1$ ~1~，所有元素只可能是平均值的下取整或上取整。记

$\displaystyle q = \left\lfloor \frac{N}{M} \right\rfloor, \qquad r = N \bmod M$

则每个元素只能取 $q$ ~q~ 或 $q + 1$ ~q + 1~。设取 $q + 1$ ~q + 1~ 的元素个数为 $r'$ ~r'~，由总和相等得到

$\displaystyle M q + r' = N \quad \Longrightarrow \quad r' = N - M q = r$

可见取 $q + 1$ ~q + 1~ 的个数恰好等于余数 $r$ ~r~，其余 $M - r$ ~M - r~ 个元素取 $q$ ~q~。因此乘积最大的方案所对应的多重集是完全确定的：由 $M - r$ ~M - r~ 个 $q$ ~q~ 与 $r$ ~r~ 个 $q + 1$ ~q + 1~ 构成。

多重集确定后，剩下的只是排列顺序问题。字典序比较从第一个元素开始，把更小的数放在前面不会更劣；而任意一对逆序相邻的元素 $(q + 1, q)$ ~(q + 1, q)~ 交换为 $(q, q + 1)$ ~(q, q + 1)~ 都会使序列的字典序变小。因此把全部 $q$ ~q~ 排在前面、全部 $q + 1$ ~q + 1~ 排在后面（即非降序排列）即为字典序最小的方案。

若改用枚举所有拆分或动态规划来求最大乘积，状态规模随拆分数目增长，在 $N \le 10^9$ ~N \le 10^9~、 $M \le 10^6$ ~M \le 10^6~ 时完全不可行；本题只需按上述公式直接构造答案。需要注意输出本身就包含 $M$ ~M~ 个数，任何做法的耗时都不会低于 $O(M)$ ~O(M)~。

具体示例

以 $N = 10$ ~N = 10~、 $M = 3$ ~M = 3~ 为例， $q = \lfloor 10 / 3 \rfloor = 3$ ~q = \lfloor 10 / 3 \rfloor = 3~， $r = 10 \bmod 3 = 1$ ~r = 10 \bmod 3 = 1~，故方案由 $3 - 1 = 2$ ~3 - 1 = 2~ 个 $3$ ~3~ 与 $1$ ~1~ 个 $4$ ~4~ 构成。三种排列中 $4, 3, 3$ ~4, 3, 3~ 与 $3, 4, 3$ ~3, 4, 3~ 的字典序都更大，故输出 $3, 3, 4$ ~3, 3, 4~。

再以 $N = 100$ ~N = 100~、 $M = 7$ ~M = 7~ 为例， $q = 14$ ~q = 14~， $r = 2$ ~r = 2~，方案由 $5$ ~5~ 个 $14$ ~14~ 与 $2$ ~2~ 个 $15$ ~15~ 构成，输出 $14, 14, 14, 14, 14, 15, 15$ ~14, 14, 14, 14, 14, 15, 15~。若换成 $4$ ~4~ 个 $13$ ~13~ 与 $3$ ~3~ 个 $16$ ~16~，总和仍为 $100$ ~100~，但最大值与最小值之差为 $3$ ~3~，乘积更小。

当 $N$ ~N~ 能被 $M$ ~M~ 整除时 $r = 0$ ~r = 0~，全部 $M$ ~M~ 个数都取 $q$ ~q~，例如 $N = 6$ ~N = 6~、 $M = 3$ ~M = 3~ 输出 $2, 2, 2$ ~2, 2, 2~；当 $M = 1$ ~M = 1~ 时输出 $N$ ~N~ 本身。

算法步骤

读入两个整数，分别存入 n 与 m。
计算 q $= \lfloor n / m \rfloor$ ~= \lfloor n / m \rfloor~ 与 r $= n \bmod m$ ~= n \bmod m~。
依次输出 $m - r$ ~m - r~ 个 q，再输出 r 个 $q + 1$ ~q + 1~，相邻两数之间用一个空格分隔，最后一个数输出后换行。

复杂度分析

时间： $O(M)$ ~O(M)~。其中计算 $q$ ~q~ 与 $r$ ~r~ 为 $O(1)$ ~O(1)~，其余开销全部来自输出 $M$ ~M~ 个数。
空间： $O(1)$ ~O(1)~ 的额外空间（不计输出缓冲）。若实现时先把答案拼接为字符串，则需 $O(M)$ ~O(M)~ 的字符空间。

实现注意事项

输出顺序必须先小后大，即先输出 $q$ ~q~ 再输出 $q + 1$ ~q + 1~；把 $q + 1$ ~q + 1~ 放在前面会得到字典序更大的方案。
每组输入对应的输出是单行、 $M$ ~M~ 个整数、以单个空格分隔、行末换行，且行末不留多余空格；用「除第一个数外每次先输出一个空格」的写法可以自然满足该格式。
数据保证 $N \ge M$ ~N \ge M~，故 $q \ge 1$ ~q \ge 1~，不会出现 $0$ ~0~ 或负数，无需特判； $r = 0$ ~r = 0~ 时全部 $M$ ~M~ 个数均为 $q$ ~q~。
不要真正计算乘积：最大乘积约为 $(N / M)^M$ ~(N / M)^M~ 量级，远超 $64$ ~64~ 位整数范围。本题只需构造方案，不需求出乘积的值。
参与运算的量本身很小： $q \le N \le 10^9$ ~q \le N \le 10^9~， $M \le 10^6$ ~M \le 10^6~， $32$ ~32~ 位整数即可容纳，C++ 中使用 long long 同样安全。
输出规模最大约 $5 \times 10^6$ ~5 \times 10^6~ 字节，C++ 需关闭流同步并使用 '\n' 而非 endl，避免每次输出都刷新缓冲区；Python 应把结果拼接成一个字符串后一次性输出，避免逐个数调用 print。
输入只有一行两个整数，注意一次性读入全部数据，不要因按行读取而只读到第一个数。

源代码

#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 q = n / m;
    long long r = n % m;

    for (long long i = 0; i < m; ++i) {
        if (i > 0) {
            cout << ' ';
        }
        cout << (i < m - r ? q : q + 1);
    }
    cout << '\n';

    return 0;
}

import sys


def main():
    n, m = map(int, sys.stdin.read().split())
    q, r = divmod(n, m)
    ans = [str(q)] * (m - r) + [str(q + 1)] * r
    sys.stdout.write(' '.join(ans) + '\n')


main()

目前没有评论。