【zzuliOJ】1912 - 小火山的爱情密码（尺取法）

FishWang

发布于 2025-08-27 10:07:13

14700

代码可运行

运行总次数：0

代码可运行

点击打开题目

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 <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define idx(x) (x-'a')
int need[27];
int have[27];
bool check()
{
    for (int i = 0 ; i <= 25 ; i++)
    {
        if (have[i] < need[i])
            return false;
    }
    return true;
}
int main()
{
    int u;
    int n,k;
    char a[10011];
    scanf ("%d",&u);
    while (u--)
    {
        CLR(need,0);
        CLR(have,0);
        scanf ("%d %d",&n,&k);
        scanf ("%s",a);
        for (int i = 1 ; i <= k ; i++)
        {
            char t[5];
            int num;
            scanf ("%s %d",t,&num);
            need[t[0] - 'a'] = num;
        }
        int st = 0;
        int ans = INF;
        for (int i = 0 ; i < n ; i++)
        {
            int id = idx(a[i]);
            have[id]++;
            if (check())
            {
                while (check())
                {
                    ans = min (ans , i - st + 1);
                    int c = idx(a[st]);
                    have[c]--;
                    st++;
                }
            }
        }
        if (ans == INF)
            printf ("-1\n");
        else
            printf ("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

scanf