思路与算法

一个三层蛋糕需要三个不同半径，原蛋糕可以任意重排。统计每个半径出现次数c。若想制作k个成品，同一种半径最多使用k次，所以可用总量为sum min(c,k)。恰能制作k个的判定条件是sum min(c,k)>=3k。

答案在0到N/3之间。可行时舍弃若干成品仍可行，所以判定单调；用上取中点的整数二分，判定可行则提高下界，否则降低上界。频次数组按1至N建立，避免对3000000个半径反复排序。

正确性说明

必要性：每个成品内半径严格递增，同一半径在一个成品至多出现一次，k个成品中每种半径至多使用k次。所有成品需要3k个蛋糕，故总容量至少3k。

充分性：若总容量至少3k，从各半径的容量内选取恰好3k个蛋糕，使每种半径选取次数不超过k。按半径排序这些选出的蛋糕，将第j个分配给编号j模k的成品。同一种半径在排序中连续出现且长度不超过k，因此不会两次分到同一成品；每个成品恰分得3个蛋糕，三者半径互异，按半径从小到大堆叠即符合严格递增。k=0显然可行。故容量条件充要。

可行的k个成品中任意舍弃一个仍是合法方案，因此可行数量是从0开始的前缀。二分始终把最大可行值保留在闭区间内，并按充要判定缩小，终止时下界就是最优答案。

复杂度

频次数组分配和初始化O(N)，读取并计数O(N)。每次判定遍历N+1个频次，O(N)；二分O(log(N+1))次，总时间O(N log(N+1))，额外空间O(N)。使用long long计算容量和3k，保留0答案及小N边界。

易错点

1. 半径要严格递增，三个相等或只有两类半径不能组成一个成品。
2. 统计的是可用总容量min(c,k)，不能简单拿总数除3。
3. 原蛋糕可重排，没有保持原输入顺序的限制。
4. k=0不需要做模k构造；只在充分性证明的k>0情形分组。
5. 覆盖N<3、单一半径、两种半径、频次极度偏斜、最大3000000规模和半径等于N。数据为独立训练数据，非官方隐藏测试。

参考代码（C++11）

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int nextInt() {
    int c = getchar_unlocked(), x = 0;
    while (c < '0' || c > '9')
        c = getchar_unlocked();
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
int main() {
    int n = nextInt();
    vector<int> f(n + 1);
    for (int i = 0; i < n; ++i)
        ++f[nextInt()];
    int lo = 0, hi = n / 3;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        long long total = 0;
        for (int x : f)
            total += min(x, mid);
        if (total >= 3LL * mid)
            lo = mid;
        else
            hi = mid - 1;
    }
    printf("%d\n", lo);
}