这里写自定义目录标题
更多精彩内容
这里是带你游历编程世界的Dashcoding编程社，我是Dash/北航硕士/ICPC区域赛全国排名30+/给你呈现我们眼中的世界！
256题算法特训课，帮你斩获大厂60W年薪offer，冲击蓝桥杯国一，ICPC/CCPC区域赛获奖
原题
2023睿抗-出院
B站动画详解
问题分析
该问题的核心是对输入的饮料名称进行分类，规则如下：
- 如果输入的是已知等级的饮料名称，直接输出该饮料对应的等级。
- 如果输入的饮料名称是由两个已知等级的饮料名称组合而成的，那么将两个部分的等级合并后输出，例如 Diet 的等级为 A，Coke 的等级为 D，那么 DietCoke 的等级为 AD。
- 如果输入的饮料名称既不是已知等级的饮料，也不能分解成两个已知的饮料组合，或者存在多种可能的分解方式，则默认输出 D 级。
要实现这一目标，我们可以使用贪心和模拟的策略：在对饮料名称进行判断时，尽可能地优先考虑唯一的有效分解方案。
具体步骤如下：
- 首先，我们用哈希表存储所有已知饮料及其对应等级，以便快速查找。
- 然后，对于需要定级的每一个饮料，首先判断它是否在哈希表中存在，若存在则直接输出对应等级。
- 如果哈希表中不存在该饮料，则尝试将其分解为两个部分，并检查两部分是否都在哈希表中存在。若存在唯一的有效分解，则输出合并后的等级；否则，输出默认等级 D。
思路分析
该问题主要采用贪心和模拟的算法进行解决。由于题目中说明每个需要定级的饮料最多只能被分解为两个部分，因此我们可以用双指针遍历整个字符串，将其从不同位置进行分割，逐一检查分割后的两个部分是否均在已知饮料的哈希表中存在。
具体的算法流程如下：
对于每一个待定级的饮料：
- 若该饮料已经在哈希表中，直接输出其等级。
- 否则，从左到右遍历饮料名称，尝试将其分解为两个部分：
- 从索引 1 开始，尝试将饮料名称切分为两部分，分别判断这两部分是否均存在于哈希表中。
- 若存在唯一的有效分解方案，合并这两部分的等级并输出。
- 如果没有有效分解方案或存在多个可能的分解方式，则默认输出 D 级。
算法实现
- 使用哈希表
map<string,string> mp存储已知饮料及其对应等级，确保查找的效率。 - 在处理需要定级的饮料时，首先检查是否存在于哈希表中，存在则直接输出。
- 如果不存在，则通过遍历尝试将饮料名称分割为两部分，并检查两部分是否均存在于哈希表中。
- 最后根据分解结果决定输出等级，如果没有找到唯一的有效分解，输出默认等级 D。
代码详解
标准代码程序
C++代码
#include<bits/stdc++.h>
using namespace std;
map<string,string>mp; // 存储已知饮料名称及其等级
int n, m; // n 表示已知饮料的数量，m 表示需要定级的饮料数量
int main(void) {
cin >> n >> m;
// 读取已知饮料及其等级
for (int i = 0; i < n; i++) {
string s1, s2;
cin >> s1 >> s2;
mp[s1] = s2;
}
// 处理需要定级的饮料
for (int i = 0; i < m; i++) {
if (i != 0)
cout << endl;
string s;
cin >> s;
// 1. 如果该饮料在已知等级中
if (mp.count(s)) {
cout << mp[s];
} else {
// 2. 尝试将其分解为两个部分
int cnt = 0; // 记录有效的分解次数
string ans;
for (int i = 1; i < s.size(); i++) {
string s1 = s.substr(0, i); // 前半部分
string s2 = s.substr(i); // 后半部分
if (mp.count(s1) && mp.count(s2)) { // 检查两部分是否都在已知饮料中
cnt++;
ans = mp[s1] + mp[s2];
}
}
// 如果没有有效分解或存在多种分解方式
if (cnt == 0 || cnt > 1)
cout << "D";
else
cout << ans;
}
}
return 0;
}
Java代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
Map<String, String> map = new HashMap<>();
for (int i = 0; i < n; i++) {
String name = scanner.next();
String level = scanner.next();
map.put(name, level);
}
for (int i = 0; i < m; i++) {
if (i != 0) System.out.println();
String drink = scanner.next();
if (map.containsKey(drink)) {
System.out.print(map.get(drink));
} else {
int count = 0;
String result = "D";
for (int j = 1; j < drink.length(); j++) {
String part1 = drink.substring(0, j);
String part2 = drink.substring(j);
if (map.containsKey(part1) && map.containsKey(part2)) {
count++;
result = map.get(part1) + map.get(part2);
}
}
if (count == 1) {
System.out.print(result);
} else {
System.out.print("D");
}
}
}
}
}
Python代码
def main():
n, m = map(int, input().split())
drink_map = {}
for _ in range(n):
name, level = input().split()
drink_map[name] = level
for _ in range(m):
drink = input()
if drink in drink_map:
print(drink_map[drink])
else:
count = 0
result = "D"
for i in range(1, len(drink)):
part1 = drink[:i]
part2 = drink[i:]
if part1 in drink_map and part2 in drink_map:
count += 1
result = drink_map[part1] + drink_map[part2]
if count == 1:
print(result)
else:
print("D")
if __name__ == "__main__":
main()
Javascript代码
function main() {
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
const input = [];
rl.on('line', line => {
input.push(line);
}).on('close', () => {
const [n, m] = input[0].split(' ').map(Number);
const drinkMap = new Map();
for (let i = 1; i <= n; i++) {
const [name, level] = input[i].split(' ');
drinkMap.set(name, level);
}
for (let i = n + 1; i < n + 1 + m; i++) {
const drink = input[i];
if (drinkMap.has(drink)) {
console.log(drinkMap.get(drink));
} else {
let count = 0;
let result = "D";
for (let j = 1; j < drink.length; j++) {
const part1 = drink.slice(0, j);
const part2 = drink.slice(j);
if (drinkMap.has(part1) && drinkMap.has(part2)) {
count++;
result = drinkMap.get(part1) + drinkMap.get(part2);
}
}
if (count === 1) {
console.log(result);
} else {
console.log("D");
}
}
}
});
}
main();
复杂度分析
时间复杂度分析
- 初始化部分：
- 读取已知饮料信息并将其存入哈希表需要 O ( N ) O(N) O(N) 的时间，其中 N N N 是已知饮料的数量。
- 查询部分：
- 对每一个需要定级的饮料（共
M
M
M 个）：
- 首先判断该饮料是否在哈希表中，这一步的时间复杂度为 O ( 1 ) O(1) O(1)。
- 如果不在哈希表中，则需要尝试将该饮料名称拆分为两部分。假设待定级饮料的长度为 L L L，我们需要进行 L − 1 L-1 L−1 次分割，每次分割需要检查两部分是否存在于哈希表中，这里的时间复杂度为 O ( L ) O(L) O(L)。
因此，处理每个待定级饮料的最坏情况时间复杂度为 O ( M × L ) O(M \times L) O(M×L)。
空间复杂度分析
- 用于存储已知饮料及其对应等级的哈希表需要 O ( N ) O(N) O(N) 的空间，其中 N N N 是已知饮料的数量。
- 需要定级的饮料字符串在存储时需要 O ( M × L ) O(M \times L) O(M×L) 的空间，其中 M M M 是需要定级的饮料数量， L L L 是饮料名称的平均长度。
综上，空间复杂度为 O ( N + M × L ) O(N + M \times L) O(N+M×L)。
总结
该问题的关键在于如何高效地对饮料名称进行分割和查找。通过使用哈希表，我们能够在常数时间内查找已知饮料及其对应等级。在处理待定级的饮料时，采用双指针将名称从不同位置进行分割，并通过哈希表判断分割后的两部分是否均在已知饮料中存在，这样的方式有效地减少了时间复杂度。
算法的整体效率相对较高，适用于输入规模较大的场景。即使在最坏情况下，算法的时间复杂度也能够控制在 O ( M × L ) O(M \times L) O(M×L)，而哈希表的使用确保了查找操作的高效性。
本题目展示了贪心策略和模拟方法在解决组合拆分问题中的应用，是一个典型的考察字符串处理、哈希查找和算法设计的编程题目。
标签：map,888,int,drink,出院,饮料,哈希,2023,等级 From： https://blog.csdn.net/Dashcoding213/article/details/141252341