单词接龙
#容器的应用 2025-02-19 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

// 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词
struct Word {
  std::string word;

  explicit Word(std::string w) : word(std::move(w)) {}

  bool operator<(const Word &right_word) const {
	  // 如果当前单词比右边的单词长，则当前单词较大
	  if (this->word.size() > right_word.word.size()) {
		  return false;
	  }
	  if (this->word.size() < right_word.word.size()) {
		  return true;
	  }
	  // 如果两个单词的长度相等，比较字典序
	  return this->word >= right_word.word;
  }
};

int main() {

	int word_start;
	cin >> word_start;
	int word_size;
	cin >> word_size;
	cin.ignore();

	vector<string> wordVec;
	unordered_map<char, priority_queue<Word>> word_table;
	for (int i = 0; i < word_size; ++i) {
		std::string word;
		getline(cin, word);
		Word w(word);
		word_table[word[0]].push(std::move(w));
		wordVec.push_back(word);
	}

	if ((word_start < 0) || (word_start >= wordVec.size())) return 0;
	std::string first_word = wordVec[word_start];
	std::string result = first_word;
	while (true) {
		char last_ch = first_word[first_word.size() - 1];
		auto it = word_table.find(last_ch);
		if (it != word_table.end()) {
			std::string pop_str = it->second.top().word;
			it->second.pop();
			result += pop_str;
			first_word.swap(pop_str);
		} else {
			break;
		}
	}

	cout << result << "\n";

	return 0;
}

这道题如果没有容器的实战经验，我不认为是可以轻松拿下的题目。

unordered_map 记录每个字符对应的单词集合，这里利用 priority_queue 进行存储。但我看到题目这样描述“当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词”的时候，我就知道要把数据放在一个结构体中，并且重载 < 运算符，并且放在 priority_queue 中，添加和删除元素都可以自动排序。

有如上的巧妙设计，解题也就不在话下了。