题目大意

有 $n$ 张邮票，每张邮票来自一个城市 $a_i$。现在要将邮票分给 $k$ 个人，要求：

• 每个人得到的邮票多重集完全相同
• 即对于每个城市，每个人得到该城市的邮票数量相同

对于每个 $k = 1, 2, \ldots, n$，求最多能分发多少张邮票。

算法思路

关键观察

1. 问题转化：设城市 $i$ 有 $cnt_i$ 张邮票。当分给 $k$ 个人时，每个人从城市 $i$ 最多能得到 $\lfloor \frac{cnt_i}{x} \rfloor$ 张邮票，其中 $x$ 是某个整数。

2. 核心思路：对于每个城市 $i$，它能贡献的邮票总数是 $cnt_i \cdot \lfloor \frac{k}{d} \rfloor$，其中 $d$ 是 $cnt_i$ 的约数。但更直接的想法是：对于固定的 $k$，每个城市最多能提供 $\lfloor \frac{cnt_i}{\lceil cnt_i / s \rceil} \rfloor$ 张邮票给每个人，其中 $s$ 是每个人从该城市得到的邮票数。

3. 高效解法：

   • 统计每个城市的邮票出现次数
   • 对于每个出现次数 $c$，考虑所有 $k$ 的倍数，计算该城市能贡献的邮票数
   • 使用差分数组累加贡献

具体解法

1. 统计频率：用哈希表统计每个城市的邮票数量，得到频率数组 $freq$

2. 预处理贡献：

   • 对于每个频率 $c$，考虑所有可能的 $k$ 值
   • 对于每个 $k \leq c$，该城市能贡献 $\lfloor c / \lceil c / k \rceil \rfloor$ 张邮票给每个人
   • 但更简单的方法：对于每个 $k$，所有频率 $c \geq k$ 的城市都能贡献邮票

3. 优化计算：

   • 使用整除分块的思想，对于每个频率 $c$，它在 $k$ 的某些区间内贡献相同
   • 用差分数组记录贡献的变化

算法步骤

1. 统计每个值的出现次数，存入cnt数组
2. 对每个出现次数c，考虑所有k <= c
3. 对于固定的k，每个人最多从该城市得到floor(c/k)张邮票
4. 因此该城市总共能贡献k * floor(c/k)张邮票
5. 用差分数组累加每个k对应的总邮票数
6. 输出结果

复杂度分析

• 时间复杂度：$O(n \log n)$，使用整除分块优化后，所有频率的总处理时间是 $O(n \log n)$
• 空间复杂度：$O(n)$

代码实现

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

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> cnt_map;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt_map[a[i]]++;
    }
    
    vector<int> cnt;
    for (auto &p : cnt_map) {
        cnt.push_back(p.second);
    }
    
    vector<ll> ans(n + 1, 0);
    
    // 对每个出现次数c，考虑它对所有k的贡献
    for (int c : cnt) {
        // 整除分块：对于k在[l, r]区间内，floor(c/k)的值相同
        for (int l = 1, r; l <= c; l = r + 1) {
            r = c / (c / l);
            int val = c / l;  // 每个人从该城市得到的邮票数
            // 该城市在k ∈ [l, r]区间内能贡献val * k张邮票
            ans[l] += val;
            if (r + 1 <= n) {
                ans[r + 1] -= val;
            }
        }
    }
    
    // 前缀和得到最终答案
    for (int k = 1; k <= n; k++) {
        if (k > 1) ans[k] += ans[k - 1];
        cout << ans[k] << (k == n ? "\n" : " ");
    }
    
    return 0;
}

样例解释

对于样例：

n = 9
邮票: 1, 1, 777, 42, 777, 1, 42, 1, 777

城市统计：

• 城市1: 4张
• 城市42: 2张
• 城市777: 3张

结果分析：

• $k=1$: 所有人得到所有9张邮票
• $k=2$: 每人得到(2张1, 1张42, 1张777)，共8张
• $k=3$: 每人得到(1张1, 0张42, 1张777)，共6张
• $k=4$: 每人得到(1张1, 0张42, 0张777)，共4张
• $k\geq5$: 无法满足条件，输出0