初始化需要背诵的文章边界int l = m + 1, r = -1;
m个单词,如果某个单词是需要背诵的,并且这个需要背诵的单词在文章中只出现了1次,它在文章中的位置是idx, 则执行:l = min(l, idx), r = max(r, idx);m个单词,如果某个单词是需要背诵的,并且这个需要背诵的单词在文章中出现的次数num次(num > 1),则在这num次中找出一个位置idx,这个位置到[l, r]区间的距离最小,执行:l = min(l, idx), r = max(r, idx);经过上边两次遍历后,题目中要求的第二问的答案就是区间[l, r]的长度,即 r - l = 1.
但我的代码只AC了1个点,求大佬改正:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
using namespace std;
map <string, int> need_rem; // num
map <string, int> s_n;
string st[1010];
int n, m;
int diff;
vector <int> weizhi[1010];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
string s; cin >> s;
st[i] = s;
need_rem[s] = -1;
s_n[s] = i;
}
cin >> m;
for (int i = 1; i <= m; i ++) {
string s; cin >> s;
if (need_rem[s] == -1 || need_rem[s] >= 1) {
if (need_rem[s] == -1) {
diff ++;
need_rem[s] = 0;
}
need_rem[s] ++;
weizhi[s_n[s]].push_back(i);
}
}
cout << diff << endl;
int l = m+1, r = -1;
for (int i = 1; i <= n; i ++) {
if (need_rem[st[i]] == 1) {
l = min(l, i);
r = max(r, i);
}
}
for (int i = 1; i <= n; i ++) {
if (need_rem[st[i]] >= 2) {
int min_dis = 0x3f3f3f3f, idx = -1;
for (auto x : weizhi[i]) {
if (x >= l && x <= r) {
min_dis = 0;
idx = x;
}
else if (x > r) {
if (x - r < min_dis) {
min_dis = x - r;
idx = x;
}
}
else {
if (l - x < min_dis) {
min_dis = l - x;
idx = x;
}
}
}
l = min(l, idx);
r = max(r, idx);
}
}
cout << r - l + 1 << endl;
return 0;
}