锐客网

  1. 首页 > it技术 > >

#|【算法小结】尺取法及例题（Subsequence，Jessica’s Reading Problem）

算法#算法小结

“ Ctrl AC！ 一起 AC！” 反复地推进区间的开头和末尾，来求取满足条件的最小区间的方法被称为尺取法 目录
例1：Subsequence
解法1：
解法2（尺取法）：
例2：Jessica's Reading Problem
解（尺取法）：

例1：Subsequence #|【算法小结】尺取法及例题（Subsequence，Jessica’s Reading Problem）
文章图片
解法1：
用sum[i]表示区间[0,i)的整数和，那么sum[t]-sum[s]就是区间[s,t)的整数和
a(0)+...+a(i-1)=sum[i]
a(s)+...+a(t-1)=sum[t]-sum[s]
这样我们只要枚举起点s，再找到一个最近的t，使得这个区间的整数和大于等于S即可（用二分），再用这个长度更新答案即可。

int n,S; int a[MAX_N]; int sum[MAX_N+1]; void solve(){ for(int i=0; i
解法2（尺取法）：
用sum记录区间和，初始时s，t为0，然后t一直加1，同时sum一直记录s到t的整数和，当sum>S时，用此时的区间长度更新答案，然后sum减去a[s]的值，s++；如果此时sum<=S，就继续移动t，直到sum>S。依次类推。
这样一直推动区间起点和终点，并记录区间状态，从而寻求答案的方法就是尺取法。
void solve(){ int res=n+1; int s=0,t=0,sum=0; while(1){ while(t

例2：Jessica's Reading Problem #|【算法小结】尺取法及例题（Subsequence，Jessica’s Reading Problem）
文章图片

解（尺取法）：
#|【算法小结】尺取法及例题（Subsequence，Jessica’s Reading Problem）
文章图片

int P; int a[MAX_P]; void solve(){ set all; for(int i=0; i count; //first是知识点标号，second是其出现次数 int res=P; //最多翻完整本书 while(1){ while(t

感谢阅读！！！
【#|【算法小结】尺取法及例题（Subsequence，Jessica’s Reading Problem）】“ Ctrl AC！一起 AC！”

    推荐阅读


    上一篇：刷遍PAT|1051 复数乘法 (15 分)

    下一篇：数据结构|劈叉都会还不会下腰吗（（二叉树经典面试题详解））