编程练习-2022-05-31-Andy

这道题思考了很久，后来和老师一起讨论，才得到完整思路
后来总是拿到42分， 参考样例代码 修改了几个细节点 才 AC
修改的细节点 在 注释的部分

题目描述

lester大神为考GRE有n（<=1000)个单词想要背，他想通过一篇文章中的一段来记住这些单词。文章由m（<=100000)个单词构成，lester想在文章中找出连续的一段，其中包含最多的他想要背的单词（重复的只算一个）。并在背诵的单词量尽量多的前提下，还要使选出的文章段落尽量短，这样他就可以用尽量短的时间学习尽可能多的单词了

样例数据

输入格式

第1行一个数n，接下来n个长度不超过10的字符串，表示一个要背的单词。下一行是一个数m，然后是m个长度不超过10的字符串，表示文章中的一个单词

输出格式

第1行为文章中最多包含的要背的单词数，第2行表示在文章中包含最多要背单词的最短的连续段的长度。如无法背任何单词输出两行0.

标签

蠕动区间

输入

3
hot dog milk
5
hot dog dog milk hot

输出

3
3

AC代码

#include <bits/stdc++.h>
using namespace std;
string x[200000],a;//x1[200000];
int cnt1=1;
map<string,int> cnt;
set <string> gre;
set <string> gre1;
int main()
{
    int sum=0,ans=1;
    int n,m;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        gre.insert(a);}
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>x[i];
        if(gre.count(x[i])){
            gre1.insert(x[i]);
            //x1[cnt1]=x[i];
            //不需要新建一个数组存文章里需要读的的单词
            cnt1++;
        }
    }
    if(gre1.empty()){
        cout<<0<<endl<<0;
        return 0;
    }
    int t=0,h=0,nn=gre1.size();
    ans+=m;
    while(1){
        while(h<m&&sum<nn){//修改：新的h上限应该是m sum上限应该是nn
            string word=x[h++];
            if(!gre.count(word))continue;
            cnt[word]++;
            if(cnt[word]==1)sum++;
        }
        if(sum<nn)break;
        ans=min(ans,h-t);
        string word=x[t++];
        if(!gre.count(word))continue;
        cnt[word]--;
        if(cnt[word]==0)sum--;
    }
    cout<<nn<<endl<<ans;
    return 0;
}