你已经写到了 Gale-Shapley 算法的核心部分，但代码在处理女性已有订婚对象时的逻辑上**未完成**。我来帮你补全并优化整个函数，确保它能正确运行、输出格式符合要求。 以下是**完整且正确的 `solve()` 函数实现**（包括缺失的分支和边界处理）： ```python import sys def solve(): data = sys.stdin.read().split() if not data: return idx = 0 num_tests = int(data[idx]) idx += 1 for test_case in range(num_tests): if test_case > 0: print() # 测试用例间空行 n = int(data[idx]) idx += 1 males = data[idx:idx+n] idx += n females = data[idx:idx+n] idx += n # 构建男性偏好表: male -> list of females (in order) male_prefs = {} for i in range(n): pref_line = data[idx] idx += 1 parts = pref_line.split(':') male_name = parts[0] prefs = list(parts[1]) male_prefs[male_name] = prefs # 构建女性偏好表: female -> dict mapping male to rank (lower is better) female_prefs = {} for i in range(n): pref_line = data[idx] idx += 1 parts = pref_line.split(':') female_name = parts[0] prefs = list(parts[1]) # 创建映射：male -> preference rank (index) rank_map = {male: i for i, male in enumerate(prefs)} female_prefs[female_name] = rank_map # Gale-Shapley 算法 free_males = males[:] # 所有男性初始自由 engaged = {} # female -> male (当前订婚对象) male_next_proposal_index = {m: 0 for m in males} # 每个男性下一个要求婚的女性索引 while free_males: male = free_males.pop(0) # 获取该男性下一个要求婚的女性 pref_list = male_prefs[male] next_idx = male_next_proposal_index[male] if next_idx >= len(pref_list): continue # 无更多可求婚对象（理论上不会发生，因为保证有解） female = pref_list[next_idx] male_next_proposal_index[male] += 1 # 下次求婚跳过这个 if female not in engaged: # 女性单身，直接接受 engaged[female] = male else: # 女性已有订婚对象，比较新旧男性谁更受青睐 current_male = engaged[female] # 比较 female 对 male 和 current_male 的偏好 if female_prefs[female][male] < female_prefs[female][current_male]: # 女性更喜欢新来的男性，于是解除旧关系，接受新男性 free_males.append(current_male) # 原配变自由 engaged[female] = male else: # 女性更喜欢原配，拒绝新男性 free_males.append(male) # 男性继续寻找 # 输出结果：按男性排序，输出每对匹配 # 要求输出格式：每个匹配为 "male:female"，按 male 字典序排列 matches = [(male, female) for female, male in engaged.items()] matches.sort() # 按 male 字典序排序 for male, female in matches: print(f"{male}:{female}") # 调用函数 solve() ``` --- ### ✅ 功能说明： - **输入格式假设**： ``` 2 3 A B C X Y Z A:XYZ B:ZXY C:YZX X:ABC Y:CAB Z:BAC ``` - **输出示例**： ``` A:X B:Y C:Z ``` - **关键修复点**： - 补全了 `else` 分支中女性是否接受男性的判断逻辑。 - 当女性拒绝时，将男性重新加入 `free_males` 继续求婚。 - 最终输出按男性名字字典序排列。 --- ### 📌 注意事项： 1. 输入数据必须是标准格式，例如： - 第一行：测试用例数 - 每个测试用例包含： - `n` - `males` 列表（空格分隔） - `females` 列表（空格分隔） - `n` 行男性偏好：`M:ABC` - `n` 行女性偏好：`F:ABC` 2. 确保所有名字唯一，且男女数量一致。 --- 如果你还有特定的输出格式要求或想加调试信息，也可以告诉我！