2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法 [2020/05/22 21:17] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法 [2020/06/02 21:58] (当前版本) shaco |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 尺取法 ====== | + | ====== 尺取法 two pointers ====== |
| - | === 简介&思想 === | + | ===== 简介&思想 ===== |
| 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。\\ | 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。\\ | ||
| - | 关注左右两端的指针，当选定的区间中所关注的值大于目标值时将左侧指针左移，当选定的区间中所关注的值小于目标值时将右指针右移，直至终点。枚举区间的复杂度为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|ouo]] | + | |
| 这道题比较基础，就充当模板了。（尺取法似乎没有特定的模板） | 这道题比较基础，就充当模板了。（尺取法似乎没有特定的模板） | ||
| - | 如果枚举两端的话复杂度就是O(n^2)。但是正数序列是单调的，也就是说扩大区间其和一定增大，减小区间其和一定减小；并且我们其实不关心每一个区间，我们关心的是和大于S的区间，而这样的区间由于单调性肯定是和越短和越小，因此对于同一个左/右位置我们关心的是使和尽可能小的但仍大于S的另一端。可能说得不是很明确，不过这道题从直觉上、一定的理性上，尺取法都是一个好的选择，而且将复杂度将至O(n)。 | + | 如果枚举两端的话复杂度就是$O(n^2)$。但是正数序列是单调的，也就是说扩大区间其和一定增大，减小区间其和一定减小；并且我们其实不关心每一个区间，我们关心的是和大于S的区间，而这样的区间由于单调性肯定是和越短和越小，因此对于同一个左/右位置我们关心的是使和尽可能小的但仍大于S的另一端。可能说得不是很明确，不过这道题从直觉上、一定的理性上，尺取法都是一个好的选择，而且将复杂度降至$O(n)$。 |
| 思路是，当选取的区间和大于S时就把左端点右移直至小于S，当区间和小于S时就将右端点右移直至大于S。等于的情况合理即可。 | 思路是，当选取的区间和大于S时就把左端点右移直至小于S，当区间和小于S时就将右端点右移直至大于S。等于的情况合理即可。 | ||
| 行 61: | 行 60: | ||
| ---- | ---- | ||
| - | === poj 3320 Jessica's Reading Problem === | + | ===== poj 3320 Jessica's Reading Problem ===== |
| - | 一本书有 P 页，每页都有a[ i ]个知识点，知识点可能重复，求最少的连续页数来覆盖所有知识点。[[http://poj.org/problem?id=3320|ouo]] | + | 一本书有 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|ouo]] | + | 给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小。数组中的数可正可负。[[http://poj.org/problem?id=2566|链接]] |
| 这个题看起来并不符合我们使用尺取法的条件。不过我们可以将其变形。 | 这个题看起来并不符合我们使用尺取法的条件。不过我们可以将其变形。 | ||
| 行 78: | 行 77: | ||
| 将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。 | 将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。 | ||
| - | [[2020-2021:teams:no_morning_training:poj2566|代码 | + | <hidden 代码> |
| - | ]] | + | <code cpp> |
| + | #include<cstdio> | ||
| + | #include<algorithm> | ||
| + | #define INF 0x3f3f3f3f | ||
| + | using namespace std; | ||
| + | int n,k,a; | ||
| + | typedef pair<int,int> unit; | ||
| + | unit sum[100005]; | ||
| + | int main() | ||
| + | { | ||
| + | while(scanf("%d%d",&n,&k)&&n) | ||
| + | { | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | scanf("%d",&a); | ||
| + | sum[i]=unit(sum[i-1].first+a,i); | ||
| + | } | ||
| + | sort(sum+1,sum+1+n); | ||
| + | for(int i=1;i<=k;i++) | ||
| + | { | ||
| + | scanf("%d",&a); | ||
| + | int t=INF,l,r; | ||
| + | for(int left=1,right=1;right<=n;right++) | ||
| + | { | ||
| + | while(sum[right].first-sum[left].first>a) | ||
| + | { | ||
| + | if(sum[right].first-sum[left].first-a<t) | ||
| + | { | ||
| + | t=sum[right].first-sum[left].first-a; | ||
| + | l=sum[left].second; | ||
| + | r=sum[right].second; | ||
| + | } | ||
| + | left++; | ||
| + | } | ||
| + | if(a-sum[right].first+sum[left].first<t) | ||
| + | { | ||
| + | t=a-sum[right].first+sum[left].first; | ||
| + | l=sum[left].second; | ||
| + | r=sum[right].second; | ||
| + | } | ||
| + | } | ||
| + | printf("%d %d %d\n",sum[r].first-sum[l].first,l,r); | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </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/知识点/基础/尺取法.1590153470.txt.gz · 最后更改: 2020/05/22 21:17 由 shaco
