P15404 [NOISG 2026 Prelim] 玲珑宝塔 题解

lucasincyber · 2026-04-02 14:44:41 · 题解

题目传送门

思路

首先，答案具有单调性，即如果 x 个塔可以被建出来，则 x - 1 个塔也一定可以被建出来。那我们考虑二分答案。问题就转化为判断是否能建造出 x 个塔。

考虑一层一层地建造这 x 个塔。维护每一个塔最后放入的大小，在填入方块的时候从小到大填。这样一定最优，因为当前填的位置一定是还未填的位置中最小的数，这样才能最大化当前方块被利用的概率。如果填不进去，直接跳过，因为后面的塔要求一定比这个塔大，就更填不进去了。最后判断一下所有塔的高度有没有都达到 k 即可。

时间复杂度 \mathcal{O}(n \log n)。二分上界可以取 \lfloor \dfrac{n}{k} \rfloor。

代码

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

const int N = 1e6 + 5;

int n, k, w;
int a[N], lst[N];

bool check(int mid)
{
    if (mid == 0) return 1;
    for (int i = 1; i <= mid; i++)
        lst[i] = -2e9;
    int cnt = 0, id = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] - lst[id] >= w)
        {
            lst[id] = a[i];
            if (id == mid)
            {
                cnt++;
                id = 1;
            }
            else id++;
        }
    }
    return (cnt >= k);
}

signed main()
{
    scanf("%lld%lld%lld", &n, &k, &w);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    int l = 0, r = n / k, res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf("%lld\n", res);
    return 0;
}