1 条题解
-
0
题解说明
问题背景:
程序读入两组字符串集合 和 ,每组字符串数量分别为 和 。
每个字符串都以小写字母开头,程序将它们按照首字母存入数组 和 ,其中下标 对应'a'
,下标 对应'b'
,依此类推。
接下来程序从 中第一个非空位置开始,按字母顺序逐一比较 与 ,并根据缺失情况和前一位的大小关系判断胜负。核心逻辑:
-
输入处理:
- 读入 和 。
- 将 个字符串放入 , 个字符串放入 ,位置由首字母决定。
- 例如
"apple"
存入 ,"banana"
存入 。
-
起始位置确定:
- 找到 中第一个非空字符串的位置 ,作为比较起点。
-
逐位比较:
- 从 开始,依次向后检查:
- 情况1:若 为空,且 ,则判定 Zoe 获胜。
- 情况2:若 为空,且 ,则判定 Leona 获胜。
- 程序在满足条件时立即输出结果并结束。
- 从 开始,依次向后检查:
-
循环终止:
- 由于程序在找到胜负时直接
return
,因此循环是一个无限循环for(;;)
,但必然会在某个条件触发时退出。
- 由于程序在找到胜负时直接
复杂度分析:
- 输入处理 。
- 比较过程最多遍历 个字母位置,复杂度 。
- 总体复杂度
#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
- 上传者