【暑期第二次训练赛】小火山的爱情密码（尺取法）

小灰灰 2022-07-19 06:12 135阅读 0赞

[点击打开题目][Link 1]

## 1912: 小火山的爱情密码 ##

Time Limit: 1 Sec Memory Limit: 128 MB  
Submit: 157 Solved: 38  
  
[Submit][] [Status][] [Web Board][]

## Description ##

小火山获得了一个字符串，然而大火山让小火山从里面截取一段字符串，并且让小火山截取的字符串满足一些字符达到一定数量。

小火山觉得很容易，但是他想要知道他至少得截取多长的字符串。

## Input ##

首先是一个整数t(t<=100)，表示测试数据组数。接下来是两个整数n和m(n<=10000, m<=10)，n表示字符串的长度，m表示要满足一定数量的字符

的种类.(字符只包含小写英文字母)

个数（没有重复字符种类），然后有m行，每行第一个是一个字符，然后是一个整数x(x<=50），表示这种字符的的要求数量。

## Output ##

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

## Sample Input ##

6 3

cancan

c 2

a 2

n 2

## Sample Output ##

## HINT ##

## Source ##

[zzuli][]

看了大牛的代码才有的思路，思路真是巧妙，自愧不如啊，多向大神学习才是好的 。

仍然是尺取法，用check检查是否满足条件。

代码如下：思路真妙，我是服了

#include<stdio.h>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    #define NTC(x,u) memset(x,u,sizeof(x))
    #define idx(x) (x-'a')
    const int INF = 0x3f3f3f3f;
    const int N = 10000+10;
    char c[N];
    int have[27],need[27];
    bool check() {
    	for(int i=0; i<26; i++) {
    		if(have[i]<need[i])
    			return false;
    	}
    	return true;
    }
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		NTC(have,0);
    		NTC(need,0);
    		int n,m,num,ans=INF;
    		scanf("%d%d",&n,&m);
    		scanf("%s",c);
    		for(int i=0; i<m; i++) {
    			char cl[5];
    			scanf("%s%d",cl,&num);
    			need[cl[0]-'a']=num;
    		}
    		int st=0;
    		for(int i=0; i<n; i++) {
    			int id=idx(c[i]);
    			have[id]++;
    			if(check()) {
    				while(check()) {
    					ans=min(ans,i-st+1);
    					id=idx(c[st]);
    					have[id]--;
    					st++;
    				}
    			}
    		}
    		if(ans==INF)
    			printf("-1\n");
    		else
    			printf("%d\n",ans);
    	}
    	return 0;
    }

[Link 1]: http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1912
[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=1912
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1912
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1912
[zzuli]: http://acm.zzuli.edu.cn/zzuliacm/problemset.php?search=zzuli