尺取法的复杂度为 O(n) ,主要应用有关连续性的问题,基本原理就是反复地推进区间的开头和末尾,来求取满足条件的最小区间,或者相似的应用。
尺取法在别的地方又被称为滑动窗口或者蠕虫算法,我觉得蠕虫算法这个名称用的相当恰当啊,就是一步一步地往后移动,一直找到答案,而不用遍历回溯什么的,也就是因为这样,他的复杂度才这么低。
举例子什么的,就直接看题目好了,搞了三个例题,看完应该会有一定的理解了吧。
该题就是让你求最短的,同时包含a b c 的字符串的长度,数据较水,好像遍历,DP 也可以过,这题用尺取法的话,时间是0 ms,也就是说还是很高效的。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char tt[1010]; int cnt[200]; int main() { while(~scanf("%s",tt)) { int len = strlen(tt); int sta = -1, ans = len; for(int i = 0; i < len; i ++) { while( (!cnt['a'] || !cnt['b'] || !cnt['c']) && sta < len - 1) { sta ++; cnt[tt[sta]] ++; } if(cnt['a'] && cnt['b'] && cnt['c']) ans = min(sta - i + 1, ans); cnt[tt[i]] --; } printf("%d\n", ans); } }
该题就是给你长度为n的整列整数a[0],a[1],……a[n-1],以及整数S,求出总和不小于S的连续子序列的长度的最小值。
你只要不断的把下标往前“ 蠕动 ” 就可以了,比如a[0],a[1]....a[k],然后a[1],a[2]....a[k],a [k+1] , 一直持续着,中间可能有多种满足状况,你要找出最短的长度即可
#include<stdio.h> #include<algorithm> #include<cstring> #include<queue> #include<cmath> using namespace std; const int INF = 0x7fffffff; int tt[100010]; int t, n, tot; int main() { while(~scanf("%d",&t)) { while(t --) { scanf("%d %d",&n, &tot); for(int i = 0;i < n; i ++) scanf("%d",&tt[i]); int sta = 0, endd = 0; // sta 到 endd 为一个区间 ,sta不断向前蠕动.... int sum = 0, ans = INF; while(1) { while(sum < tot && endd < n) { sum += tt[endd ++]; } if(sum < tot) break; ans = min(ans, endd - sta); sum -= tt[sta ++]; } if(ans == INF) printf("0\n"); else printf("%d\n",ans); } } return 0; }
NBUT 1576 炒鸡想减肥的字符串
该题感觉稍微复杂一点,但是和第一题几乎一模一样,要注意的是,但m 为3 的时候,就不能考虑d, e , f, 什么的,这题题意我看错了三次,还好最后还是一A,直接上代码了(该解法还是RANK 的第一 其它的解法好像也有0ms 的, 大神请一定分享一下啊 ,在下感激不尽) 好吧,其实你会发现judge 的两个函数一样的,cnt 和nut的重复,自己再改一下好了,这是比赛的代码知己贴上去了- 。 -
#include<stdio.h> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; const int N = 100010; char tt[1010]; int cnt[1110]; // 看是否出现过该字符 int nut[1110]; int t, a, b; int num; int judge() { for(int i = 0; i < b; i ++) { if(!cnt['a' + i]) return 1; } return 0; } int judge1() { for(int i = 0; i < b; i ++) { if(!nut['a' + i]) return 1; } return 0; } int main() { while(~scanf("%d",&t)) { while(t --) { memset(cnt, 0, sizeof(cnt)); memset(nut, 0, sizeof(nut)); scanf("%d%d",&a,&b); scanf("%s",tt); int sta = -1, ans = a; for(int i = 0; i < a; i ++) { // num = 0; while(judge() == 1 && sta < a) { sta ++; cnt[tt[sta]] ++; nut[tt[sta]] ++; // printf("AA %d %c %d %d \n", sta, tt[sta], num , b); // num = 0; } if(judge() == 0) ans = min(sta - i + 1, ans); cnt[tt[i]] --; // printf("%d %d %d\n",sta, i, ans); } if(judge1() == 0 || ans < a) printf("%d\n",ans); else printf("I am so fat!\n"); } } return 0; }
------------------------------------------- 渣渣的算法路 , 大神勿喷, 欢迎一起交流 , 有事请留言