请问这种思路对不对?
  • 板块P1381 单词背诵
  • 楼主52wyd
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/6 16:04
  • 上次更新2023/10/23 16:31:57
查看原帖
请问这种思路对不对?
816549
52wyd楼主2023/5/6 16:04

初始化需要背诵的文章边界int l = m + 1, r = -1;

  1. 遍历文章中的m个单词,如果某个单词是需要背诵的,并且这个需要背诵的单词在文章中只出现了1次,它在文章中的位置是idx, 则执行:l = min(l, idx), r = max(r, idx);
  2. 遍历文章中的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;
}



2023/5/6 16:04
加载中...