[原创]Codeforces Round #364 div.2 C. They Are Everywhere 【尺追法】

2016-07-23 11:33:07 Tabris_ 阅读数：872

博客爬取于2020-06-14 22:44:08
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52003317

题目连接 ：http://codeforces.com/problemset/problem/701/C

-----------------------------------.
C. They Are Everywhere
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Sergei B., the young coach of Pokemons, has found the big house which consists of n flats ordered in a row from left to right. It is possible to enter each flat from the street. It is possible to go out from each flat. Also, each flat is connected with the flat to the left and the flat to the right. Flat number 1 is only connected with the flat number 2 and the flat number n is only connected with the flat number n - 1.

There is exactly one Pokemon of some type in each of these flats. Sergei B. asked residents of the house to let him enter their flats in order to catch Pokemons. After consulting the residents of the house decided to let Sergei B. enter one flat from the street, visit several flats and then go out from some flat. But they won’t let him visit the same flat more than once.

Sergei B. was very pleased, and now he wants to visit as few flats as possible in order to collect Pokemons of all types that appear in this house. Your task is to help him and determine this minimum number of flats he has to visit.

Input
The first line contains the integer n (1 ≤ n ≤ 100 000) — the number of flats in the house.

The second line contains the row s with the length n, it consists of uppercase and lowercase letters of English alphabet, the i-th letter equals the type of Pokemon, which is in the flat number i.

Output
Print the minimum number of flats which Sergei B. should visit in order to catch Pokemons of all types which there are in the house.

Examples
input
3
AaA
output
2

input
7
bcAAcbc
output
3

input
6
aaBCCe
output
5

Note
In the first test Sergei B. can begin, for example, from the flat number 1 and end in the flat number 2.

In the second test Sergei B. can begin, for example, from the flat number 4 and end in the flat number 6.

In the third test Sergei B. must begin from the flat number 2 and end in the flat number 6.

-----------------------------------------------------------------------------.

题目大意 ：有N个公寓里面住着口袋妖怪 ，下面给了N个公寓中每个公寓里的口袋妖怪的是哪一种 （分别用大小写字母表示 共52种） 你只能从其中的任意一个公寓进去，然后出去，然而呢 邻近的公寓与公寓之间是相通的 你可以从左边的公寓不出去就走到右边的公寓 问你如果一个人想要收集全所有出现过得所有种的口袋妖怪最少要经过多少个公寓，每种口袋妖怪有一个即可。。

解题思路：根据题意 ，N比较大 所以暴力三层for 会TLE 之后仔细看了下题 很明显的尺追法

维护两个指针 代表区间的左右界
按要求不断维护 更新最值即可

/********/ 换一种画风来描述这个问题

如果子串(i,j)包含了所有种个不同的字符，那么子串(i,k),(j < 9 < length)也包含了至少个不同字符。

因此对于每一个左边界，只要找到最小的满足条件的右边界，就能找到以这个左边界开始的符合条件的子串的长度的最小值。

寻找这个右边界，是经典的追赶法（尺取法,双指针法）问题。维护两个指针（数组下标），轮流更新左右边界，更新最值即可。复杂度 O(N)。

详情看代码注释吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# include <iostream>
# include <stdio.h>
# include <algorithm>
# include <math.h>
# include <string>
# include <string.h>
using namespace std;

# define LL __int64
# define INF 0x1f1f1f1f

char a[101010];
int h[130],pre[130];

int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",a+1);

    memset(h,0,sizeof(0));
    memset(pre,0,sizeof(pre));

    for(int i=1;i<=n;i++)
        h[a[i]]=1;

    int sum=0;//记录一共有多少种pokemon
    for(int i='a',j='A';i<='z';i++,j++)
        sum+=h[i]+h[j];

    // 尺追法
    int mini = n , num = 0;//num记录区间内有多少pokemon
    int l=1,r=1;//左右的区间界限
    while(l<=r&& r<n)
    {
        while(num<=sum && r<=n)
        {
            if(pre[a[r]]<l)   //根据pre知道这个pokemon 之前出现的位置
                num++;
            pre[a[r]]=r;  //更新位置

            if(num==sum)       mini=min(mini,r-l+1);//更新最小值

            if(num>=sum||r>=n) break;//当区间内满足num==sum or r==n 的时候右界限就不应该被继续维护 应该去维护左界限
            r++;
        }

        while(l<=r&&num>=sum)
        {
            if(pre[a[l]]==l)//如果这个pokemon在区间内只出现在左界限这里 那么此区间就不能在缩小了 就应该跳出 继续回去维护右界限
            {
                mini=min(mini,r-l+1);//更新最小值
                num--,l++;
                break;
            }
            //如果这个pokemon在区间内"不"只出现在左界限这里 那么左界限就可以向右+1 来缩小区间的范围  此时num依然等于sum
            mini=min(mini,r-l+1);//更新最小值
            l++;
        }
    }
    printf("%d/n",mini);
    return 0;
}