题解 | #图书分类#

题目链接

题目描述

小美图书馆需要根据图书的标题 $s$ 和页数 $p$ 来分类。请根据以下规则判断每本图书的类别，规则按顺序检查，如果符合多个，只取第一个匹配的。

儿童图书 (Children)：标题以 "Child" 开头（不区分大小写），且页数 $p \le 100$ 。
科技图书 (Tech)：标题以 "Tech" 开头（不区分大小写），且页数 $p > 200$ 。
小说 (Novel)：标题包含 "Novel"（不区分大小写），无论页数多少。
其他情况 (Other)：返回 "Other"。

输入第一行为一个整数 $n$ ( $1 \le n \le 100$ )，表示有 $n$ 本图书。此后 $n$ 行，每行依次输入一个由大小写字母混合组成的字符串 $s$ ( $1 \le \text{length}(s) \le 20$ ) 和一个整数 $p$ ( $1 \le p \le 10^3$ )。

解题思路

本题是一个典型的多条件分支问题。我们需要遍历 $n$ 本书，对每一本书都应用题目给定的分类规则。

核心要点是严格遵循规则的 优先级顺序。我们可以使用 if-else if-...-else 的级联判断结构来实现这一点，确保每个图书只会被归入第一个满足条件的类别。

另外，题目要求字符串匹配不区分大小写。一个通用且简单的处理方法是：在进行比较前，将读入的标题字符串 $s$ 统一转换为全小写或全大写。

具体解题步骤如下：

读取图书总数 $n$ 。
进入一个循环，执行 $n$ 次。
在循环中，读取每本书的标题 $s$ 和页数 $p$ 。
将标题 $s$ 转换为全小写，得到一个新的字符串 lower_s。
条件一：判断 lower_s 是否以 "child" 开头并且 $p \le 100$ 。若满足，则输出 "Children"。
条件二：若不满足上一条件，则判断 lower_s 是否以 "tech" 开头并且 $p > 200$ 。若满足，则输出 "Tech"。
条件三：若不满足以上条件，则判断 lower_s 是否包含子串 "novel"。若满足，则输出 "Novel"。
其他情况：若以上所有条件均不满足，则输出 "Other"。
对每本书处理完毕后，换行以便处理下一本。

代码

c++
java
python

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        string s;
        int p;
        cin >> s >> p;
        
        string lower_s = s;
        // 就地将字符串副本转换为小写
        transform(lower_s.begin(), lower_s.end(), lower_s.begin(), ::tolower);
        
        // C++20 提供了 starts_with, 但为了兼容性，此处使用 substr
        if (lower_s.rfind("child", 0) == 0 && p <= 100) {
            cout << "Children" << endl;
        } else if (lower_s.rfind("tech", 0) == 0 && p > 200) {
            cout << "Tech" << endl;
        } else if (lower_s.find("novel") != string::npos) {
            cout << "Novel" << endl;
        } else {
            cout << "Other" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            int p = sc.nextInt();
            
            String lower_s = s.toLowerCase();
            
            if (lower_s.startsWith("child") && p <= 100) {
                System.out.println("Children");
            } else if (lower_s.startsWith("tech") && p > 200) {
                System.out.println("Tech");
            } else if (lower_s.contains("novel")) {
                System.out.println("Novel");
            } else {
                System.out.println("Other");
            }
        }
    }
}

n = int(input())
for _ in range(n):
    # 接收一行输入并分割
    line = input().split()
    s = line[0]
    p = int(line[1])
    
    lower_s = s.lower()
    
    if lower_s.startswith('child') and p <= 100:
        print('Children')
    elif lower_s.startswith('tech') and p > 200:
        print('Tech')
    elif 'novel' in lower_s:
        print('Novel')
    else:
        print('Other')

算法及复杂度

算法：字符串处理、多条件分支判断。
时间复杂度： $\mathcal{O}(N \cdot L)$ ，其中 $N$ 是图书的总数， $L$ 是标题字符串的最大长度。对于每本书，都需要进行一次小写转换（成本 $\mathcal{O}(L)$ ）和最多三次字符串匹配操作。字符串匹配（如 startsWith, contains）的时间复杂度也与 $L$ 相关。
空间复杂度： $\mathcal{O}(L)$ ，主要开销用于存储单本图书的标题字符串。因为每次循环只处理一本书，所以空间是复用的。