CF1988A Split the Multiset 题解

题意简述

初始多重集 $S=\{n\}$，每次操作可以：

1. 选择 $S$ 中的一个正整数 $u$；
2. 移除它的一个副本；
3. 向 $S$ 中插入 不超过 $k$ 个正整数，它们的和等于 $u$。

求使 $S$ 中恰包含 $n$ 个 $1$ 所需的最小操作次数。

$1 \le n \le 1000$，$2 \le k \le 1000$。

核心思路

每次操作相当于把一个大数“分裂”成若干小数，且分裂出的数的个数不超过 $k$。

初始时集合中只有 $1$ 个元素，最终我们需要 $n$ 个元素（全部是 $1$）。
一次操作最多可以把 $1$ 个元素变成 $k$ 个元素，因此每操作一次，元素总数最多增加 $k-1$。

要从 $1$ 个元素变成 $n$ 个元素，至少需要操作

次。这就是所需答案的下界。

构造方案（证明下界可达）

我们可以采用如下贪心策略：

• 每次选取当前集合中最大的数 $x$（且 $x>1$）。
• 若 $x \ge k$，将其分裂为 $k$ 个数：$(\underbrace{1,1,\dots,1}_{k-1\text{ 个}}, x-(k-1))$。
• 若 $x < k$，则将其直接分裂为 $x$ 个 $1$（此时不再有大于 $1$ 的数，过程结束）。

这样，每次操作（除最后一次外）都会恰好产生 $k-1$ 个新的 $1$，同时保留一个剩余的大数供后续处理。最终，当剩余的那个数小于 $k$ 时，最后一次操作将其全部变成 $1$。

因此，总操作次数恰好为 $\lceil (n-1)/(k-1) \rceil$，达到下界。

答案公式

• 当 $n = 1$ 时，答案为 $0$。
• 否则答案为 $\lceil (n-1) / (k-1) \rceil$。

在整数运算中可写成 (n - 1 + k - 2) / (k - 1) 或直接使用 ceil。

复杂度分析

• 时间复杂度：$O(1)$ 每组数据。
• 空间复杂度：$O(1)$。

参考代码

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

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

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (n == 1) {
            cout << "0\n";
        } else {
            cout << (n - 1 + k - 2) / (k - 1) << '\n';
        }
    }
    return 0;
}