题解：SP25780 VISIBLEBOX - Decreasing Number of Visible Box

Lonely_Peak · 2025-06-10 16:49:28 · 题解

做题思路

对于这道题目，我们需要找到最少需要展示的盒子数量。

核心思路是将盒子按大小降序排序，然后使用贪心策略构建隐藏链。每个盒子要么作为新链的起点，要么添加到现有链的末端。最终，链的数量就是需要展示的盒子数量。

那么这道题我们可以这样做：

• 先将盒子从大到小按降序排列，这样可以从最大的盒子开始处理；
• 然后使用一个多重集合来维护每条链的最内层盒子（即链中最小的盒子）。
• 接着在集合中查找第一个大于等于当前盒子大小两倍的链头。如果找到了，则更新该链的最内层盒子为当前盒子。如果未找到，则以当前盒子作为新链的起点。
• 最终集合的大小即为链的数量，也就是需要展示的盒子数量。

参考代码

#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(nullptr),std::cout.tie(nullptr)
using namespace std;
int a[100005];
bool cmp(int x, int y) {
    return x > y;
}
signed main() {
    fast_running;
    int T, cnt = 0;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1, cmp);
        multiset<int> h;
        for (int i = 1; i <= n; i++) {
            auto it = h.lower_bound(2 * a[i]);   //对于每个盒子x，在h中查找第一个大于等于2*x的链头。
            if (it != h.end()) {   //如果找到，则删除该链头，并将x插入集合（更新该链的最内层盒子）。
                h.erase(it);
                h.insert(a[i]);
            } else {               //如果未找到，则将x作为新链的起点插入集合。
                h.insert(a[i]);
            }
        }
        cout << "Case " << ++cnt << ": " << h.size() << '\n';
    }
    return 0;
}

[]()