题解：CF2091D Place of the Olympiad

Eysiking · 2025-03-26 08:05:24 · 题解

CF2091D Place of the Olympiad 题解

实际上是个简单的数学题，用到了鸽笼原理。大意是说 n 个物品放入 k 个盒子，则至少有一个盒子放入的物品数至少为 \lceil \frac{n}{k}\rceil 个。

回到这题，显然一行放得越多，可能拼凑出的长度越大，那么数量最多的一行至少有 \lceil \frac{n}{k}\rceil 个桌子，我们肯定不希望有两个空位连在一起造成浪费，那么该行会有 m-\lceil \frac{n}{k}\rceil 个空位，于是该行的 \lceil \frac{n}{k}\rceil 个作为物品放入 m-\lceil \frac{n}{k}\rceil+1 个位置中，再用一次鸽笼原理，连缀起来的最长桌子是 \lceil\frac{\lceil \frac{n}{k}\rceil}{m-\lceil \frac{n}{k}\rceil+1}\rceil。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    cout << m / (m - (k + n - 1) / n + 1) << "\n";
}