题解：SP25780 VISIBLEBOX - Decreasing Number of Visible Box

做题思路

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

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

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

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

参考代码

CPP

#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;
}

题解：SP25780 VISIBLEBOX - Decreasing Number of Visible Box

文章操作

做题思路

参考代码

相关推荐

评论

题解：SP25780 VISIBLEBOX - Decreasing Number of Visible Box