取尺法，又被叫做双指针法，一般可以用来维护具有单调性质的序列,所以有些题目取尺法和二分都可以用，但取尺法的复杂度还是优于二分的。
实现方式
1.维护两个指针
2.直接stl 的queue 来进行维护取尺法
总的来说,用第二种相对更好写，但stl略慢一点。
我下面刷的取尺法题目难度主要在cf的1500,1600左右。
下面上例题
1.Hard Process http://codeforces.com/contest/660/problem/C
0,1两种序列，最多经过k次0->1变化，问改变后最长相同路径1的长度。
这道题单调性质在于从贪心的思路来看，变换一定是是相邻的。比如我们可以维护一个queue，遇到1可以直接插入，遇到0的话，不满k次，也直接插入，当等于k时，我们需要统计当前queue的大小即长度，然后queue释放出0后，再插入0。
code：http://codeforces.com/contest/660/submission/45268215
相同题目:Vasya and String http://codeforces.com/contest/676/problem/C
2.洛谷P1638 逛画展
这个比上面这个更明显，就是维护k。
code:https://www.luogu.org/record/show?rid=13053507
基本相同题目：http://codeforces.com/contest/701/problem/C
3.洛谷 P1102 A−B数对
这个题也简单
code：https://www.luogu.org/record/show?rid=13058178
待补
网友评论