尺取

98 阅读 0 评论 65 点赞

我是靠谱客的博主优雅康乃馨，最近开发中收集的这篇文章主要介绍尺取，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

常用在需要在给的一组数据中找到不大于某个上限的优先子序列

比如：给长度为n的数组和一个整数m，求总和不小于m的连续子序列的最小长度

那么我们先用sum存当前这个子序列的和，从左边第一个数来存，直到这个子序列的和大于等于m为止，再记录下当前长度。当不满足条件就入队，然后得到队列长度，再将队首元素出队，再进行下一次的入队，直到满足条件再次出队，并且将这一次的长度与历史最短长度进行取舍，最后扫到最后的元素却无法再满足入队条件的时候就结束。

while(T--)

{

cin>>n>>max;

for(int i = 0 ; i < n ; i++)

cin>>a[i];

int i = 0,j = 0,sum = 0,ans = n+1;

while(1)

{

while(j < n && sum <= max)

sum += a[j++];

if(sum < max) break;

ans = min(j-i,ans);

sum -= a[i++];

}

if(ans > n)ans = 0;

printf("%dn",ans);

}

给出一个字符串，求该字符串的一个子串s，s包含A-Z中的全部字母，并且s是所有符合条件的子串中最短的，输出s的长度。如果给出的字符串中并不包括A-Z中的全部字母，则输出No Solution。

Input

第1行，1个字符串。字符串的长度 <= 100000。

Output

输出包含A-Z的最短子串s的长度。如果没有符合条件的子串，则输出No Solution。

Sample Input

BVCABCDEFFGHIJKLMMNOPQRSTUVWXZYZZ

Sample Output

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char s[100005];
int a[100]={0};
int main()
{
    int k,i,j,ans,sum;
    memset(a,0,sizeof(a));
    scanf("%s",s);
    k=strlen(s);
    i=0;j=0;ans=k+1;sum=0;
    while(j<k||sum==26)
    {
        while(j<k&&sum<26)
        {
        if(a[s[j]-65]==0)
            {
             sum++;
            }
            a[s[j]-65]++;
            j++;
        }
        if(sum==26)
        ans=min(ans,j-i);
        if(a[s[i]-65]<=1)
            sum--;
        a[s[i]-65]--;
        i++;
    }
    if(ans==k+1)
        printf("No Solutionn");
    else
        printf("%dn",ans);
    return 0;
}