题解：P16544 [EGOI 2026] 蛋糕 / Cakes

zhang_kevin · 2026-05-18 17:47:53 · 题解

记 V = \max a_i。

考虑一种方案合法的充要条件是什么。假设众数的出现次数为 t，则不能存在一种配料的出现次数 a_i > t \cdot K（否则众数就超过 t 了），这等价于 t \geq \frac{V}{K}；另一方面，不能存在一个蛋糕没有足够的配料可用，即 \sum\limits_{i = 1}^n \lfloor \frac{a_i}{t} \rfloor \geq K。显然 t 越小对第二个条件越好，因此直接让 t 取到 \lceil \frac{V}{K} \rceil，带入第二个条件可以得到：

于是我们得到了 \mathcal{O}(nq) 的做法，下面考虑优化。

看到 \lceil \frac{V}{K} \rceil，可以联想到整除分块。我们把 K 按照阈值 \sqrt{V} 分成大 K 和小 K，然后分别处理：

1. 对于大 K：此时 \lceil \frac{V}{K} \rceil \leq \sqrt{V}，因此直接把所有 \lceil \frac{V}{K} \rceil 对应的左式的值全预处理出来存下，然后直接查表即可。

2. 对于小 K：此时 K 只有 \sqrt{V} 种，因此直接预处理即可。

综上，总时间复杂度为 \mathcal{O}(n \sqrt{V} + q)，可以通过。

参考代码：

namespace Solution{
    int n, q, a[100005], V; ll small[100005], big[100005];
    inline void Solve(){
        rd(n, q); fo(i, 1, n) rd(a[i]), V = max(V, a[i]);
        const int B = sqrtl(V) + 5;
        fo(K, 1, B) fo(i, 1, n) small[K] += a[i] / (int)ceil(1.0 * V / K);
        fo(t, 1, B) fo(i, 1, n) big[t] += a[i] / t;
        while(q--){
            ll K; rd(K);
            if(K <= B){
                wrs(small[K] >= K ? "YES" : "NO"), pc('\n');
            }else{
                wrs(big[(int)ceil(1.0 * V / K)] >= K ? "YES" : "NO"), pc('\n');
            }
        }
        return;
    }
}