[POI2018]Prawnicy

[POI2018]Prawnicy
这题可以采用贪心策略,假如我们已经确定了最终区间的左端点L,那么我们选择的区间一定是左端点在L左边,且右端点最右的K个点。所以我们将所有区间按左端点排序,用小根堆维护左端点在左边,且右端点最大的K个点。每次用第K大值更新答案即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注