题目
题目描述
小明为了通过大学英语六级,小明每天都在背单词。有一天,他想到了一个奇怪的背单词办法:背文章!具体方法如下:
对于一天,预设 N 个需要背的单词,为了简略,我们在此将它们转换为单词编号,这 N 个单词编号分别为 ai。接下来给定共有 M 个单词的一长段文章,为了简略,已经将其中所有单词替换为单词编号。现在要在这一长段文章中,找到连续的一小段,使这一小段中尽可能多的包含这一天要背的单词,且在尽可能多的情况下,单词数量越少越好,求这一小段的最小单词数量是多少。
题目和字符串完全无关哦~
输入
输入第一行一个整数 N,表示这天要背的单词的数量。(1 <= N <= 1000)
接下来一行,输入 N 个整数,表示这一天要背的单词的编号 ai。( 0 <= ai <= 100000)
接下来一行一个整数 M,表示长文章中的单词数量。(1 <= M <= 100000)
最后一行输入 M 个整数,表示文章中的单词编号 bi。( 0 <= bi <= 100000)
输出
输出共两个整数,中间用空格隔开,分别表示最多背诵的单词数量和最短的连续文章单词数量。
题目限制
时间限制:C/C++语言 1000MS;其他语言 3000 MS
内存限制:C/C++语言 65536KB;其他语言 589824KB
样例输入
4
6 2 3 4
10
1 3 5 4 1 7 2 3 3 99
样例输出
3 5
思路
- 首先想到的是:两重循环暴力解决;必超时 !!!
- 由数据规模知道,此题时间复杂度为O(n) 或 O(nlgn)能过;
- 首先记录需要记的单词个数,进行文章单词输入时,记录每个要记的单词出现次数;然后在文章单词进行滑动窗口
- 具体思路看代码
代码演示
#include
int n, m, vis[100002]; // 标记要记的单词和记录文章要记的单词数量
int tp_vis[100002]; // 滑动窗口用来记录窗口中每个单词的数量
int cnt, ans;
int num[100003];
int main() {
scanf("%d", &n); //需要记的单词个数
for (int a, i = 0; i < n; i++) {
scanf("%d", &a);
vis[a] = 1; //标记需要记的单词
}
scanf("%d", &m); // 文章单词个数
for (int i = 0; i < m; i++) {
scanf("%d", &num[i]);
if (vis[num[i]] == 1) {
vis[num[i]] = 2; // 2表示文章中含有这个要记的单词
++cnt; // 窗口单词容量最大值
}
}
/*********ans表示最短的连续文章的单词个数,cnt表示最多背诵单词的个数*********/
ans = m;
if (cnt == 0) { // 题目的坑
ans = 0;
}
int l = 0, now = 0;
for (int i = 0; i < m; i++) {
if (vis[num[i]] != 2) continue; //说明文章没有这个单词
tp_vis[num[i]]++; //这个单词在文章出现的计数器加一
if (tp_vis[num[i]] != 1) continue; //这个单词不是第一次出现
now++; //窗口里出现要记的单词数量+1
while (now == cnt) {
ans = (ans > i - l + 1 ? i - l + 1 : ans);
tp_vis[num[l]]--;
if (tp_vis[num[l]] == 0) now--;
l++;
}
}
printf("%d %d\n", cnt, ans);
return 0;
}
/*
4
6 2 3 4
10
1 3 5 4 1 7 2 3 3 99
*/