zzuli 1912 小火山的爱情密码

Description

小火山获得了一个字符串，然而大火山让小火山从里面截取一段字符串，并且让小火山截取的字符串满足一些字符达到一定数量。 小火山觉得很容易，但是他想要知道他至少得截取多长的字符串。

Input

首先是一个整数t(t<=100)，表示测试数据组数。接下来是两个整数n和m(n<=10000, m<=10)，n表示字符串的长度，m表示要满足一定数量的字符 的种类.(字符只包含小写英文字母) 个数（没有重复字符种类），然后有m行，每行第一个是一个字符，然后是一个整数x(x<=50），表示这种字符的的要求数量。

Output

输出最小长度，如果达不到要求输出-1

Sample Input

16 3cancanc 2a 2n 2

Sample Output

6

尺取法，作者个体的时候，不知道什么事尺取法，但是思路差不多。但是没有过。

后来百度看别人的代码，自己又写了一遍。

相当于两个指针扫了一遍，

我的K指针为前指针，for循环的i为后指针。

没次判断能否挪动前指针。记录最小长度。

实践证明，，这个要比二分的快。

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <stack> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; #define LL long long #define N 10010 #define mod 1000000007 char a[N]; int need[30],have[30]; int judge() { for(int j=0;j<26;j++) if(have[j]<need[j]) return 0; return 1; } int main() { int T,n,m; scanf("%d",&T); while(T--) { memset(have,0,sizeof(have)); memset(need,0,sizeof(need)); scanf("%d%d",&n,&m); scanf("%s",a); char c,t; int ans=99999999,k=0,nu,d; for(int i=0;i<m;i++) { scanf("%c%c%d",&c,&t,&d); need[t-'a']=d; } for(int i=0;i<n;i++) { nu=a[i]-'a'; have[nu]++; if(judge()) while(judge()) { ans=min(ans,i-k+1); int temp=a[k]-'a'; have[temp]--; k++; } } if(ans==99999999) printf("-1\n"); else printf("%d\n",ans); } return 0; }