Codeforces Round #364 (Div.2) C:They Are Everywhere（双指针/尺取法）

题目链接：

http://codeforces.com/contest/701/problem/C

---

题意：

给出一个长度为n的字符串，要我们找出最小的子字符串包含所有的不同字符。

---

分析：

1.尺取法，不懂得可以看今天开始学算法系列-尺取法

2.二分法，具体见代码

PS：因为讲得太少所以附上A和B的题解：

A：结构体存储，将所有数sort一下，一头一尾输出即可

B：开辆个数组记录当前行或列是否有车，row[],col[],设两个变量a,b记录行列，放入一个车时，如果已标记则不用减去，否则减去（a--或b--),输出a*b即可。

---

代码：

//尺取法
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

char inp[100010];
int ch[300];

int main()
{
    int n,s,e,i,poke = 0,curpoke = 0,res = n;
    scanf("%d",&n);getchar();scanf("%s",inp);
    for(i = 0; i < n; i++) ch[inp[i]]++;

    for(i = 0; i < 256; i++)if(ch[i])poke++;
    for(i = 0; i < 256; i++)ch[i] = 0;
    s=e=0;
    while(s <= e && e <= n)
    {
        if(curpoke < poke)
        {
            if(ch[inp[e]] == 0) curpoke++;
            ch[inp[e]]++; e++;
        } 
        else 
        {
            if(ch[inp[s]] == 1)  curpoke--;
            ch[inp[s]]--;
            s++;
        }
        if(poke == curpoke) res = min(res, e - s);
    }
    printf("%d",res);
}

//二分求解 
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll __int64
#define PI acos(-1.0)
#define mod 1000000007
using namespace std;
int n;
map<char,int> mp;
map<char,int> gg;
char a[100005];
int zong;
bool check(int xx)
{
    int zha=0;
    gg.clear();
    for(int i=1;i<=xx;i++)
    {
        if(gg[a[i]]==0)
        zha++;
        gg[a[i]]++;
    }
    if(zha>=zong)
        return true;
   for(int i=xx+1;i<=n;i++)
   {
       if(gg[a[i]]==0)
            zha++;
       gg[a[i]]++;
       gg[a[i-xx]]--;
       if(gg[a[i-xx]]==0)
        zha--;
       if(zha>=zong)
       return true;
   }
   return false;
}
int main()
{
    zong=0;
    scanf("%d",&n);
    getchar();
    mp.clear();
    for(int i=1;i<=n;i++)
    {
        scanf("%c",&a[i]);
        if(mp[a[i]]==0)
        {
          mp[a[i]]=1;
          zong++;
        }
    }
    int l=zong,r=n,mid=0;
    while(l<r)
    {
        mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d
",l);
    return 0;
}