2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法 [2020/06/02 21:56] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法 [2020/06/02 21:58] (当前版本) shaco |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。\\ | 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。\\ | ||
| 关注左右两端的指针，当选定的区间中所关注的值大于目标值时将左侧指针右移，当选定的区间中所关注的值小于目标值时将右指针右移，直至终点。枚举区间的复杂度为O(n)，计算区间的值的复杂度通常是O(1)，不排除有例外。\\ | 关注左右两端的指针，当选定的区间中所关注的值大于目标值时将左侧指针右移，当选定的区间中所关注的值小于目标值时将右指针右移，直至终点。枚举区间的复杂度为O(n)，计算区间的值的复杂度通常是O(1)，不排除有例外。\\ | ||
| - | 在这个过程中间接枚举了每个区间，但与直接枚举并不同，在尺取法应用的问题中一般对区间有要求，较短的区间往往无法符合要求因此将它们包含的较大的区间枚举到即可。\\ | + | 在这个过程中间接枚举了每个区间，但与直接枚举并不同，在尺取法应用的问题中一般对区间有要求，较短的区间往往无法符合要求因此将包含它们的较大的区间枚举到即可。\\ |
| 看几个例题 | 看几个例题 | ||
| - | ---- | + | ===== poj 3061 Subsequence ===== |
| - | ==== poj 3061 Subsequence ==== | + | |
| 给定一个正数序列，使得其和大于或等于S，求最短的子序列长度。[[http://poj.org/problem?id=3061|链接]] | 给定一个正数序列，使得其和大于或等于S，求最短的子序列长度。[[http://poj.org/problem?id=3061|链接]] | ||
| 行 61: | 行 60: | ||
| ---- | ---- | ||
| - | ==== poj 3320 Jessica's Reading Problem ==== | + | ===== poj 3320 Jessica's Reading Problem ===== |
| 一本书有 P 页，每页都有$a[i]$个知识点，知识点可能重复，求最少的连续页数来覆盖所有知识点。[[http://poj.org/problem?id=3320|链接]] | 一本书有 P 页，每页都有$a[i]$个知识点，知识点可能重复，求最少的连续页数来覆盖所有知识点。[[http://poj.org/problem?id=3320|链接]] | ||
| 行 70: | 行 69: | ||
| 代码略。 | 代码略。 | ||
| - | ==== poj 2566 Bound Found ==== | + | ===== poj 2566 Bound Found ===== |
| 给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小。数组中的数可正可负。[[http://poj.org/problem?id=2566|链接]] | 给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小。数组中的数可正可负。[[http://poj.org/problem?id=2566|链接]] | ||
| 行 128: | 行 127: | ||
| </hidden> | </hidden> | ||
| ---- | ---- | ||
| - | ==== 总结 ==== | + | ===== 总结 ===== |
| 运用尺取法一定要注意题目中序列的特征，因为尺取法并不能真正枚举每一个区间。 | 运用尺取法一定要注意题目中序列的特征，因为尺取法并不能真正枚举每一个区间。 | ||
| 对序列进行变换也可能让尺取法可以应用。 | 对序列进行变换也可能让尺取法可以应用。 | ||
| - | === 参考 === | + | ===== 参考 ===== |
| [[https://blog.csdn.net/lxt_lucia/article/details/81091597]] | [[https://blog.csdn.net/lxt_lucia/article/details/81091597]] | ||
2020-2021/teams/no_morning_training/shaco/知识点/基础/尺取法.1591106191.txt.gz · 最后更改: 2020/06/02 21:56 由 shaco
