区 间 最 优 覆 盖 问 题 区间最优覆盖问题 区间最优覆盖问题 Description 给出一个长度为 L e n Len Len 的区间 A A A, 再给出 N N N 个不同的区间 求 A A A 一次性最多覆盖多少区间, 并且输出该方案的 A A A左端点下标
给出一个长度为 L e n Len Len 的区间 A A A, 再给出 N N N 个不同的区间 求 A A A 一次性最多覆盖多少区间, 并且输出该方案的 A A A左端点下标
Solution 首先舍弃那些长度比 L e n Len Len大的区间, 设每个区间左端点 L L L, 右端点 R R R, 然后使用每个区间对差分数组进行更新: 在 R − L e n + 1 R-Len+1 R−Len+1位置加 1 1 1 在 R + 1 R+1 R+1位置减 1 1 1 最后使用该区间从左往右扫一遍, 中间取最大值即可
首先舍弃那些长度比 L e n Len Len大的区间, 设每个区间左端点 L L L, 右端点 R R R, 然后使用每个区间对差分数组进行更新:
最后使用该区间从左往右扫一遍, 中间取最大值即可
牛客博客，记录你的成长
京公网安备 11010502036488号