取尺法

取尺法,又被叫做双指针法,一般可以用来维护具有单调性质的序列,所以有些题目取尺法和二分都可以用,但取尺法的复杂度还是优于二分的。

实现方式
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
待补

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 这个不错分享给大家,从扣上看到的,就转过来了 《电脑专业英语》 file [fail] n. 文件;v. 保存文...
    麦子先生R阅读 6,685评论 5 24
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,793评论 0 33
  • 何清才刚下山不到三个时辰,便被茶馆里说书人刚刚讲完的故事惊得脸色苍白。待说书人收起摊子背上招旗,何清突的站起来,酒...
    珊橙子阅读 193评论 0 0
  • 一直的费力不讨好的说教和恐吓,在孩子身上是没有任何好的作用,而有效的教育,需从走心开始。美国著名亲子教育...
    ee978d8b1e98阅读 104评论 0 1
  • [话筒]时光飞逝,转眼间已经大学毕业。四年前的今天我也是一名焦虑的高考一员,迈进考场的拿去考卷的那一刻,心里也是五...
    share01阅读 313评论 0 0