关于第二问贪心
查看原帖
关于第二问贪心
644963
ln001楼主2024/10/29 16:56

赛时想到对区间先按照左端点排序,再按照右端点排序。

再维护后缀最小值数组 fif_i 表示对于所有排序后编号大于等于i的区间的右端点的最小值。

单开一个变量表示当前使用的最靠后的测速仪,逐个枚举每一个区间 ii,若该测速仪已经被包含则跳过。否则使用最靠后的,且位置不超过 fif_i 的测速仪。

不知道对不对,求大佬hack

2024/10/29 16:56
加载中...