题目

灵梦有 n 个单词想要背,但她想通过一篇文章中的一段来记住这些单词。
文章由 m 个单词构成,她想在文章中找出连续的一段,其中包含最多的她想要背的单词(重复的只算一个)。并且在背诵的单词量尽量多的情况下,还要使选出的文章段落尽量短,这样她就可以用尽量短的时间学习尽可能多的单词了。

输入

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

输出

输出文件共 2 行。第 1 行为文章中最多包含的要背的单词数,第 2 行表示在文章中包含最多要背单词的最短的连续段的长度。
样例输入
3
hot
dog
milk
5
hot
dog
dog
milk
hot
样例输出
3
3

思路

map+贪心
有时候,看见这种题目,就觉得 map 这种东西简直太好了。如果你不知道 map 是什么的话,推荐一个神犇的博客:http://www.cnblogs.com/rjgcs/p/5721873.html
那么,我们先用 map 将每一个要背的单词变成一个数字,这样处理起来会方便很多。不要背的单词就是 0 啦。
我们开始读入文章,我开了一个数组 ar,我不会告诉你这是 artcle 的缩写的,用于记录我们现在 “所背的” 单词表。jl 是用于记录我们背的单词在单词表中最后一次出现的位置,jjl 则是记录该单词在文章中的位置。(注意,我说的单词表不是指要背的单词!!!是指 ar 数组!!!)假如发现文章中有一个要背的单词,我们就把这个单词加入单词表,单词表记录的是这个单词 map 映射出来的值。
我们读入一个新单词的时候,会出现以下情况:
1. 如果这个单词不在所背的单词表里。
那么为了背更多的单词,我们需要把这个单词加入单词表中。更新一下 ans1 和 ans2 的值。
2. 如果这个单词在单词表里
没关系,大胆地将单词加入单词表中吧,如果单词表的长度扩展了,你不用更新 ans 的值。
3. 如果此时队首单词的出现数不为 1 了,就后移队首指针,直到为 1 为止。(注意判断队首单词是不用背的单词的情况)
就拿样例来说吧。
要背的单词是:hot(1),dog(2),milk(3)。
现在我们读入文章,第一个单词是 hot,此时 ans1=1,an2=1。
第二个单词是 dog,ans1=2,ans2=2。
第三个还是 dog, 所以不更新 ans,只将该单词放入 ar 中。
第四个是 milk,ans1=3,ans2=4。
第五个是 hot,将单词放入 ar 中,那么我们就需要将 ar 数组首指针 head 后移一位,指向 dog,而队伍中存在其它的 dog, 所以再后移一位。head=3。
更新得到 ans1=3,ans2=3。
代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<map>
using namespace std;
int n,m,tot,l=1,r=0,ok;
map<string,int>ma;
string s;
int ans1,ans2;
int vis[1005],num[1005],t[100005];
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        cin>>s;
        if(!ma[s])ma[s]=++tot;
    }
    scanf("%d",&m);
    for(i=1;i<=m;++i){
        cin>>s;
        ++r;
        if(ma.count(s)){
            t[i]=ma[s];
            if(!num[t[i]])++ans1,ans2=r-l+1;
            ++num[t[i]];
        }
        while(l<=r&&(num[t[l]]>1||num[t[l]]<=0))--num[t[l]],++l;
        ans2=min(ans2,r-l+1);
    }
    printf("%d\n%d",ans1,ans2);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注