题目回顾

我们需要实现一个简化的 Hay Point 系统来计算员工的薪资。给定一个 Hay Point 字典（包含单词及其对应的美元价值）和多个职位描述，对于每个职位描述，计算其中所有出现在字典中的单词的价值之和。未出现在字典中的单词价值为 0。

输入格式

• 第一行输入两个正整数：m（字典中的单词数量，m ≤ 1000）和 n（职位描述的数量，n ≤ 100）。
• 接下来的 m 行，每行包含一个单词（由最多 16 个小写字母组成）和一个美元价值（0 到 1,000,000 的整数）。
• 接下来的 n 个职位描述，每个描述由一行或多行文本组成，文本只包含字母、数字和空格，每个描述以单独的一行 "." 结束。

输出格式

对于每个职位描述，输出其对应的薪资，即所有出现在字典中的单词的价值之和。

解题思路

1. 读取字典：使用 $map$ 或 $unordered_map$ 来存储单词及其对应的价值，以便快速查找。
2. 处理职位描述：
   • 逐个读取单词，直到遇到 "." 结束当前职位描述。
   • 对于每个单词，检查是否存在于字典中，若存在则累加其价值。
3. 输出结果：对于每个职位描述，输出累加后的总价值。

代码解析

#include <map>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int m, n;
    map<string, int> dict; // 使用map存储单词及其价值
    cin >> m >> n; // 读取字典大小m和职位描述数量n
    int i;
    string word;
    int nValue;
    for (i = 0; i < m; ++i)
    {
        cin >> word >> nValue; // 读取单词及其价值
        dict[word] = nValue; // 存入字典
    }
    for (i = 0; i < n; ++i)
    {
        int sum = 0; // 初始化当前职位描述的总价值
        while (cin >> word && word != ".")
        {
            if (dict.find(word) != dict.end()) // 检查单词是否在字典中
            {
                sum += dict[word]; // 累加价值
            }
        }
        cout << sum << endl; // 输出当前职位描述的总价值
    }
    return 0;
}

示例验证

以题目中的输入为例：

1. 字典：

   • administer 100000
   • spending 200000
   • manage 50000
   • responsibility 25000
   • expertise 100
   • skill 50
   • money 75000

2. 职位描述 1：

   • "the incumbent will administer the spending of kindergarden milk money and exercise responsibility for making change he or she will share responsibility for the task of managing the money with the assistant whose skill and expertise shall ensure the successful spending exercise ."
   • 出现的字典单词及价值：
     • administer 100000
     • spending 200000
     • responsibility 25000（出现两次，共 50000）
     • manage 50000
     • money 75000
     • skill 50
     • expertise 100
   • 总价值：100000 + 200000 + 25000*2 + 50000 + 75000 + 50 + 100 = 700150

3. 职位描述 2：

   • "this individual must have the skill to perform a heart transplant and expertise in rocket science ."
   • 出现的字典单词及价值：
     • skill 50
     • expertise 100
   • 总价值：50 + 100 = 150

复杂度分析

• 时间复杂度：
  • 字典构建：O(m log m)，因为 $map$ 的插入操作是 O(log m)。
  • 职位描述处理：对于每个职位描述，假设平均有 w 个单词，查找每个单词的时间是 O(log m)，总时间为 O(n w log m)。
• 空间复杂度：
  • 字典存储：O(m)，存储 m 个单词及其价值。
  • 其他：O(1)，仅使用常数额外空间。

总结

通过使用 $map$ 存储字典并逐个处理职位描述中的单词，可以高效地计算出每个职位描述的 Hay Point 总价值。代码简洁明了，适用于题目给定的输入规模。