第3题 单词选择 查看测评数据信息
我们都知道,学习知识单词最好的方法就是在相应的句子和语言环境中去学习它。小W最近定下了一个学习单词的计划,他有n个单词要背,但他想在通过背一篇文章中的一段来记住这些单词
假定现在小W手头有篇包含m个单词的文章,现在他想在文章中找出连续的一段,其中包含最多的他所要背的单词重复的只算一个),并且使这段连续的单词长度最短。这样他就可以用尽量短的时间学习到尽可能多的单词了。
输入格式
第一行一个数n(1<=n<=1000)
接下来n行每行是一个长度不超过10的字符串,表示一个要背的单词。
接着是一个数m(1<=m<=100000)
然后是m行长度不超过10的字符串,每个表示文章中的一个单词。
输出格式
两行,第一行为文章中最多包含的要背的单词数,第二行表示在文章中包含最多要背单词的最短的连续段的长度。
输入/输出例子1
输入:
3
hot
dog
milk
5
hot
dog
dog
milk
hot
输出:
3
3
样例解释
无
我的程序:
#include<bits/stdc++.h>
using namespace std;
long long n,m,cnt,mi=1e18,l=1,ss[100005],cnt1;
map<string,long long> sum;
string a[100005],s[100005];
char b[100000+10][15];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++) {
scanf("%s",&b[i]);
sum[b[i]]++;
if(sum[b[i]]==1) {
cnt++;
s[cnt]=a[i];
}
}
cout<<cnt<<"\n";
cnt1=0;
for(int i=1;i<=m;i++) sum[b[i]]=0;
for(int r=1;r<=m;r++) {
sum[b[r]]++;
cnt1+=(sum[b[r]]==1);
if(cnt1==cnt) mi=min(mi,r-l+1);
while(cnt1>=cnt&&r-l+1>cnt) {
cnt1-=(sum[b[l]]==1);
sum[b[l]]--;
l++;
}
}
if(cnt1==cnt) mi=min(mi,m-l+1);
cout<<mi;
return 0;
}
调了半天,玄2关