第二行至N+1行: 每一行一个闭区间覆蓋问题输出选择的区间覆盖问题的数目,不可能办到输出-1
这道题输入数据很多请用scanf而不是cin
这道题的目的是为了从给定的n个区间覆盖问題内,选择出数目最少的区间覆盖问题使其能够覆盖一条指定线段。这道题可以采用贪心的思想来解决很明显,当两个区间覆盖问题起点一样的时候越长的区间覆盖问题能够覆盖线段的部分越长,因此这道题目我们贪的是区间覆盖问题超过线段起点的长度选最长的。
首先我们对给定的区间覆盖问题进行处理当区间覆盖问题与线段没有交集时,这些区间覆盖问题对题目而言是毫无用处的我们将这個区间覆盖问题舍弃,而将可能有用的区间覆盖问题存入到一个vector数组中vector变量类型是表示区间覆盖问题的结构体,将所有变量输入结束后我们对这个vector数组sort排序,重写比较函数按照起点从小到大排序,当区间覆盖问题起点一样时则按照区间覆盖问题终点从大到小排序。
對区间覆盖问题处理结束之后我们按照给的起点从前向后遍历数组,选出区间覆盖问题终点减去线段起点长度最长的那个区间覆盖问题然后将区间覆盖问题数加一,新的起点设立为这个区间覆盖问题终点加一因为这道题是整点覆盖,若不注意就会出错若是我们在遍曆数组的过程中发现没有一个区间覆盖问题的起点是小于等于这个起点,那么就证明覆盖不了这里注意我们设立一个int型的now,用以表示我們遍历数组时的起点now最初为0,之后now更新为我们遍历数组得到的长度最长的区间覆盖问题在vector中的ID同时为了遍历过程中当我们碰到区间覆蓋问题的起点长于给的起点时,就可以停止遍历了因为接下来的一定不符合目前的需求,他们不能覆盖起点这些操作都是为了减少不必要的耗时。
区间覆盖问题覆盖问题可以采用贪心思想来解决选择好合适的贪心标准极为重要。
要注意审题这道题是整点覆盖,不要莣记
为了减少耗时,可以首先处理好没有必要的区间覆盖问题即与线段没有交集的区间覆盖问题,还要注意遍历的起始位置和终点位置的选择这些操作可以有效地减少耗时。
在对于一个函数传入参数时要注意引用和非引用的区别,非引用的话会调用复制构造函数哆次复制构造会消耗极大的时间,如我下面的getMaxSection函数传入参数vector变量时没有引用,导致多次复制构造一直超时。