1 条题解

  • 0
    @ 2025-10-16 13:43:05

    题解说明

    问题背景:
    程序读入两组字符串集合 AABB,每组字符串数量分别为 nnmm
    每个字符串都以小写字母开头,程序将它们按照首字母存入数组 a[]a[]b[]b[],其中下标 11 对应 'a',下标 22 对应 'b',依此类推。
    接下来程序从 a[]a[] 中第一个非空位置开始,按字母顺序逐一比较 a[i]a[i]b[i]b[i],并根据缺失情况和前一位的大小关系判断胜负。

    核心逻辑:

    1. 输入处理

      • 读入 nnmm
      • nn 个字符串放入 a[]a[]mm 个字符串放入 b[]b[],位置由首字母决定。
      • 例如 "apple" 存入 a[1]a[1]"banana" 存入 a[2]a[2]
    2. 起始位置确定

      • 找到 a[]a[] 中第一个非空字符串的位置 stst,作为比较起点。
    3. 逐位比较

      • i=sti=st 开始,依次向后检查:
        • 情况1:若 a[i]a[i] 为空,且 b[i1]>a[i1]b[i-1] > a[i-1],则判定 Zoe 获胜
        • 情况2:若 b[i]b[i] 为空,且 a[i1]>b[i1]a[i-1] > b[i-1],则判定 Leona 获胜
      • 程序在满足条件时立即输出结果并结束。
    4. 循环终止

      • 由于程序在找到胜负时直接 return,因此循环是一个无限循环 for(;;),但必然会在某个条件触发时退出。

    复杂度分析:

    • 输入处理 O(n+m)O(n+m)
    • 比较过程最多遍历 2626 个字母位置,复杂度 O(1)O(1)
    • 总体复杂度
    #include <bits/stdc++.h>
    using namespace std;
    
    #define N 1000005  // 字符串最大长度
    #define M 30       // 字母相关数组大小(26个小写字母+预留)
    
    /**
     * 快速读入整数函数
     * 功能:高效读取整数,支持正负号
     * @return 读取到的整数(含符号)
     */
    int read() {
        int w = 0, f = 1;  // w: 结果值,f: 符号(1为正,-1为负)
        char c = ' ';
    
        // 跳过非数字字符,处理符号
        while (c < '0' || c > '9')
            c = getchar(), f = c == '-' ? -1 : f;  // 若遇到'-',符号设为-1
    
        // 读取数字字符,转换为整数
        while (c >= '0' && c <= '9')
            w = w * 10 + c - 48, c = getchar();  // 累加数字(c-48等价于c-'0')
    
        return w * f;  // 返回带符号的结果
    }
    
    int n, m, st;               // n: a数组的字符串数量;m: b数组的字符串数量;st: 起始比较位置
    char s[N];                  // 临时存储输入字符串的缓冲区
    string a[M], b[M];          // a、b数组:按首字母索引存储字符串(索引1对应'a',2对应'b'...)
    
    signed main() {
        n = read(), m = read();  // 读取n和m
    
        // 读取n个字符串到a数组:按首字母分类存储
        for (int i = 1; i <= n; i++) {
            scanf("%s", s);  // 读取字符串到缓冲区s
            // 首字母转换为索引('a'->1, 'b'->2...),将字符串存入a对应位置
            a[s[0] - 'a' + 1] = (string)s;
        }
    
        // 读取m个字符串到b数组:同样按首字母分类存储
        for (int i = 1; i <= m; i++) {
            scanf("%s", s);
            b[s[0] - 'a' + 1] = (string)s;
        }
    
        // 找到a数组中第一个非空字符串的位置,作为起始比较位置st
        for (int i = 1; i < M && !st; i++) {
            if (a[i] != "")  // 找到第一个有字符串的位置
                st = i;
        }
    
        // 从起始位置st开始,按字母顺序(a->b->c...)依次比较
        for (int i = st;; i++) {
            // 情况1:a[i]为空,且前一个位置b[i-1] > a[i-1] → Zoe获胜
            if (a[i] == "" && b[i - 1] > a[i - 1])
                return puts("Zoe"), 0;
    
            // 情况2:b[i]为空,且前一个位置a[i-1] > b[i-1] → Leona获胜
            if (b[i] == "" && a[i - 1] > b[i - 1])
                return puts("Leona"), 0;
        }
    
        return 0;
    }
        
    
    • 1

    信息

    ID
    3172
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者