刚结束的洛谷比赛的题解中一个小疑惑
  • 板块学术版
  • 楼主Zxsoul
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/8/18 20:33
  • 上次更新2023/11/4 10:09:40
查看原帖
刚结束的洛谷比赛的题解中一个小疑惑
230808
Zxsoul楼主2021/8/18 20:33

EE 题,题解中说到一个典型的贪心问题,可是我不对,所以来问一下。

有一个长度为 nn 的数轴和一些区间,数轴上有一些黑点,你要选最少的区间,满足每个黑点至少被一个区间包含

这是一个经典的贪心问题,我们从左往右考虑所有黑点,如果它还未被覆盖,就在所有覆盖它的区间中选出右端点最靠右的一个区间,可以 O(n)O(n) 贪心解决

我有个疑惑,在枚举黑点的时候怎么判断黑点被那些区间覆盖呀,还有就是怎么判断他是否被覆盖,对区间标号并打标记吗,还是怎么做,求大佬解答

2021/8/18 20:33
加载中...