问题 D. 切割数组（Cutting Out）

问题重述

你有一个长度为 $n$ 的数组 $s$。
你需要找到一个长度为 $k$ 的数组 $t$，使得可以从 $s$ 中完整切出尽可能多的 $t$ 的副本。

• 切出一个 $t$ 的副本意味着：从 $s$ 中取出 $t$ 的每个元素（按值，不按顺序），每个元素用一次。
• $t$ 中允许重复元素。
• 目标是最大化可以切出的副本数。

核心思路

这个问题不能直接贪心，因为 $t$ 的长度 $k$ 固定，但 $t$ 中每个数可以重复多次。
我们需要决定：最多能切出多少份（设份数为 $x$），然后根据 $x$ 构造 $t$。

关键观察

• 如果我们能切出 $x$ 份，那么对于某个数值 $v$，它在 $s$ 中的出现次数为 $cnt[v]$，则它在 $t$ 中最多可以出现 $\lfloor \frac{cnt[v]}{x} \rfloor$ 次。
• 所有数值贡献的次数之和必须 $\ge k$，才能构造出长度为 $k$ 的 $t$。
• 如果 $x$ 可行，那么 $x-1$ 也可行（单调性）。因此可以二分答案。

算法步骤

1. 统计频率
   用一个数组 $cnt$ 记录每个数值在 $s$ 中出现的次数。数值范围 $\le 2 \cdot 10^5$。

2. 二分最大份数
   二分 $x$ 的可能范围：$[1, n]$。

   • 检查函数 can(x)：
     遍历所有出现过的数值 $v$，累加 $total = \sum \lfloor \frac{cnt[v]}{x} \rfloor$。
     若 $total \ge k$，则 $x$ 可行（可以凑出长度 $k$ 的 $t$）。

3. 找到最大可行 $x$
   二分结束后得到最大的 $x_{max}$。

4. 构造 $t$
   再次遍历所有数值 $v$，将 $v$ 重复 $\lfloor \frac{cnt[v]}{x_{max}} \rfloor$ 次加入答案数组，直到答案长度达到 $k$。

复杂度分析

• 频率统计：$O(n + M)$，$M$ 为值域（$2 \cdot 10^5$）。
• 二分：$\log n \approx 18$ 次检查。
• 每次检查：遍历所有不同数值，最多 $M$ 次，$O(M)$。
• 总复杂度：$O((n + M) \log n)$，足够快。

示例解析

示例 1

$s = [1,2,3,2,4,3,1],\ k=3$

• 频率：$1:2,\ 2:2,\ 3:2,\ 4:1$
• 二分最大 $x$：
  • $x=2$：$\lfloor 2/2 \rfloor + \lfloor 2/2 \rfloor + \lfloor 2/2 \rfloor + \lfloor 1/2 \rfloor = 1+1+1+0 = 3 \ge 3$ ✅
  • $x=3$：$\lfloor 2/3 \rfloor \times 3 + \lfloor 1/3 \rfloor = 0+0+0+0 = 0 < 3$ ❌
• 最大 $x=2$。
• 构造 $t$：
  从每个数取 $\lfloor cnt / 2 \rfloor$ 个：
  取 $1,2,3$ 各一个，得到 $t=[1,2,3]$。

输出：1 2 3

代码实现（C++）

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

const int MAXV = 200005;

int n, k;
int cnt[MAXV];
vector<int> vals; // 存储出现过的数值

bool can(int x) {
    long long total = 0;
    for (int v : vals) {
        total += cnt[v] / x;
    }
    return total >= k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (cnt[x] == 0) vals.push_back(x);
        cnt[x]++;
    }

    // 二分最大份数
    int lo = 1, hi = n, ans = 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (can(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    // 构造答案 t
    vector<int> res;
    for (int v : vals) {
        int take = cnt[v] / ans;
        while (take-- && res.size() < k) {
            res.push_back(v);
        }
    }

    for (int i = 0; i < k; i++) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}

易错点提醒

1. 二分边界：最大可能份数是 $n$（当 $k=1$ 且所有元素相同时）。
2. 检查函数 can(x)：累加可能超过 $k$，但只需判断是否 $\ge k$，不需要精确值。
3. 构造时：只需取前 $k$ 个，不必完全用完所有可用次数。
4. 数值范围：频率数组开到 $200005$ 足够。