题目
题目描述
小明为了通过大学英语六级，小明每天都在背单词。有一天，他想到了一个奇怪的背单词办法：背文章！具体方法如下：
对于一天，预设 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
*/
