PTA L2-028秀恩爱分得快测试点3解析：-0陷阱与AC解法

最近群里又有人被 L2-028 秀恩爱分得快 卡住一问基本都是同一个位置测试点3。这道题在 PTA 天梯赛练习里算知名度很高的一题不是因为算法难而是因为它在一个你想不到的地方埋了雷。这篇文章就专门把测试点3讲透顺带把整道题的思路、AC代码和几个容易忽略的输出细节一起梳理出来。不管你是刚刷到这道题的新手还是WA到怀疑人生的老手这篇应该都能帮你省下不少时间。1. 先把题目规则拆开看1.1 照片里的亲密度是怎么累加的题目设定其实不复杂。现在有 N 个人编号从 0 到 N-1女性编号用负数表示。然后给出 M 张照片每张照片里有 K 个人。规则是一张照片里任意两个人之间亲密度都增加 1/K。举个例子一张照片里有 4 个人那么这 4 个人任意两人之间的亲密度都加 1/4。同一张照片里的两个人亲密度就累加没在同一张照片里出现过亲密度就是 0。这个“两两之间都加”的规则意味着亲密度计算天然就是 O(K^2) 级别的操作后面我们再说怎么优化。这里有一个非常容易忽略的细节亲密度累加的时候是不分性别的。同性的两个人出现在同一张照片里亲密度照加不误只是最后筛选“最亲密异性”的时候才把同性过滤掉。有人会在累加阶段就自作聪明地只加异性结果就是答案错误而且这种错误很难肉眼排查因为样例往往很温和。题目最后会给你两个人 A 和 B要求判断他们是不是“秀恩爱”。这里的判断标准不是看他们俩亲密度有多高而是看他们是不是彼此亲密度最高的异性。而且注意“最高”允许并列也就是说如果 A 有多个异性都达到了最高亲密度那这些人都算候选。1.2 输出规则才是真正的细节输出规则是这道题另一个大坑。如果 A 是 B 亲密度最高的异性之一同时 B 也是 A 亲密度最高的异性之一那么这两人互相符合直接输出一行“A B”结束。如果不符合互相条件那就不能只输出一对。你需要先把 A 的所有最亲密异性全部输出每行一对再把 B 的所有最亲密异性全部输出每行一对。也就是说哪怕 A 只有一个最亲密异性如果它不是 B你也得输出 A 和它的候选然后再输出 B 和它的候选。这个分支逻辑看着简单但很多人会在“互相符合”时多输出几行或者在“不符合”时漏掉 A 的候选列表里那个 B。要记住互选输出一行就走人不互选就必须把 A、B 两侧候选全部列完。输出的编号必须保留正负号。比如女性 3 号要输出 -3男性 0 号要输出 0女性 0 号要输出 -0。这个“负零”就是后面测试点3 的核心先记住它。多个并列候选的输出顺序要按照编号绝对值递增。因为编号是 0 到 N-1对应绝对值也是 0 到 N-1所以最简单的做法就是在最后收集候选时直接从小到大遍历数组下标这样天然满足顺序要求。2. 解题思路不需要算完整亲密度矩阵2.1 为什么两张一维表就够了很多第一次写这道题的人第一反应是开一个 N*N 的二维数组把所有照片里任意两人的亲密度都累加一遍最后再查 A 和 B 相关的数据。这个思路没问题但效率很尴尬。最坏情况下 M1000每张照片 K500两层循环把所有 pair 累加一遍复杂度是 O(M*K^2)也就是 1000 * 500 * 500 2.5 亿次操作。虽然 C 在极限数据下也许能擦着边过但时间很不稳而且代码写起来也更繁琐。换一个角度想题目最后只要 A 和 B 这两个人的最亲密异性列表。一张照片里如果既没有 A也没有 B那这张照片里产生的所有亲密度无论加给谁都不会出现在 A 或 B 的亲密值里所以整张照片可以直接跳过。这样一来每张照片只需要判断是否包含 A 或 B如果包含就只给 A 的亲密值数组或者 B 的亲密值数组累加。复杂度直接降到 O(M*K)而且代码少写一层循环思路也清爽很多。这里要特意说明一下我们的做法是只维护两个一维数组affA[i] 表示编号 i 的人与 A 之间的亲密度affB[i] 表示编号 i 的人与 B 之间的亲密度。每张照片如果包含 A就把照片里除了 A 以外的所有人都给 affA 加上 1/K如果包含 B就把除了 B 以外的所有人都给 affB 加上 1/K。如果 A 和 B 同时出现在一张照片里那么两个数组都要更新。2.2 累加时的小心机累加值用 double 就够了因为最终只是比较大小不需要精确输出小数。但比较的时候千万别直接写 affA[i] bestA浮点数累加会有微小误差很可能会因为精度问题把真正并列的候选漏掉。正确做法是设一个 EPS比如 1e-8判断两个数之差小于 EPS 就认为相等。累加阶段不用管性别同性和异性都加到对应数组里最后筛选时再根据性别过滤。这样可以避免在累加时写一堆性别判断还容易写错。还有一个小优化输入的最后一行才是 A 和 B但照片数据里可能包含 A 或 B。所以最好是先把所有照片都读进来解析好存成结构体再统一处理。这样后面想怎么遍历都方便。3. 测试点3的真相-0 不是 03.1 为什么用 int 读会炸很多人这道题卡测试点3卡到怀疑人生本地测试全对一提交就是 WA。原因几乎都出在输入解析上具体说就是题目里的 -0。如果读 ID 时直接用 int 变量去接收比如 cin id那么输入 -0 的时候int 拿到的是 0。这个 0 本身没错但问题在于-0 表示的是“女性 0 号”性别信息丢了。如果你后面再用这个 id 去判断性别程序就会默认它是男性 0 号或者至少分不清它到底是男 0 还是女 0。更极端的场景是A 是男性 0 号B 是女性 0 号也就是输入分别是 0 和 -0。如果都用 int 读程序里 A 和 B 的 id 都变成了 0程序会以为这两个是同一个人。后面所有涉及 A、B 是否在同一张照片、是否是异性的判断全部乱套亲密度自然算不对输出自然也错。测试点3 就是专门为这个场景准备的。它会在数据里安排 -0 这种特殊输入专门惩罚那些图省事用 int 读 ID 的人。3.2 正确的读取姿势正确做法非常简单所有 ID 一律用字符串读入然后手动解析。解析函数只需要做两件事判断字符串首字符是不是 -是的话就标记为女性把后面的数字部分转成 int 作为编号如果首字符是 -就从下标 1 开始截取。举个例子输入字符串是 -0首字符是 -所以这个人是女性编号是 stoi(0) 0。输入字符串是 0首字符不是 -所以是男性编号也是 0。这样 -0 和 0 就彻底区别开了。输出的时候也要写成函数根据性别和编号生成最终的字符串。尤其是女性 0 号必须输出 -0不能用简单的 0 代替。如果你偷懒写 printf(-%d)遇到男性 0 号就会错误地输出 -0同样会 WA。3.3 测试点3在考什么边界从测试角度来看测试点3 考的是“边界值”和“输入表示的歧义”。-0 在数学上和 0 没区别但在题目语义里负号代表着性别一个负号就能改变角色身份。程序语言里的整数类型会自动丢弃负零的符号这种“底层类型吞掉语义信息”的情况是最容易出 bug 的地方。这也解释了为什么这道题的通过率不算高。算法本身不难但输入解析和输出格式里藏着足够多的坑一个不留神就翻车。4. 完整 AC 代码与关键行解析4.1 C 全代码直接先贴一份能过的完整代码我加了注释后面再逐段解释关键点。#include bits/stdc.h using namespace std; struct Person { int id; bool female; }; Person parsePerson(const string s) { // 输入统一按字符串读避免 -0 的符号信息丢失 if (!s.empty() s[0] -) { return {stoi(s.substr(1)), true}; } return {stoi(s), false}; } string formatPerson(int id, bool female) { // 输出也要保留符号尤其是 -0 if (female) { if (id 0) return -0; return - to_string(id); } return to_string(id); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorPerson photos(m); vectorint sex(n, -1); // 1 表示女性0 表示男性-1 表示还没出现过 auto recordSex [](const Person p) { sex[p.id] p.female ? 1 : 0; }; for (int i 0; i m; i) { int k; cin k; photos[i].resize(k); for (int j 0; j k; j) { string s; cin s; photos[i][j] parsePerson(s); recordSex(photos[i][j]); } } string sa, sb; cin sa sb; Person A parsePerson(sa); Person B parsePerson(sb); recordSex(A); recordSex(B); vectordouble affA(n, 0.0), affB(n, 0.0); for (const auto photo : photos) { bool hasA false, hasB false; for (const auto p : photo) { if (p.id A.id p.female A.female) hasA true; if (p.id B.id p.female B.female) hasB true; } // 如果照片里既没有 A 也没有 B那这张照片和 A/B 都没关系 if (!hasA !hasB) continue; double add 1.0 / (double)photo.size(); if (hasA) { for (const auto p : photo) { if (p.id A.id p.female A.female) continue; affA[p.id] add; } } if (hasB) { for (const auto p : photo) { if (p.id B.id p.female B.female) continue; affB[p.id] add; } } } const double EPS 1e-8; double bestA -1.0, bestB -1.0; for (int i 0; i n; i) { if (sex[i] -1) continue; if (sex[i] ! (A.female ? 1 : 0)) bestA max(bestA, affA[i]); if (sex[i] ! (B.female ? 1 : 0)) bestB max(bestB, affB[i]); } bool bIsBestOfA (sex[B.id] ! (A.female ? 1 : 0)) fabs(affA[B.id] - bestA) EPS; bool aIsBestOfB (sex[A.id] ! (B.female ? 1 : 0)) fabs(affB[A.id] - bestB) EPS; if (bIsBestOfA aIsBestOfB) { cout formatPerson(A.id, A.female) formatPerson(B.id, B.female) \n; } else { // 从小到大遍历数组正好满足编号绝对值递增的输出要求 for (int i 0; i n; i) { if (sex[i] -1 || sex[i] (A.female ? 1 : 0)) continue; if (fabs(affA[i] - bestA) EPS) { cout formatPerson(A.id, A.female) formatPerson(i, sex[i] 1) \n; } } for (int i 0; i n; i) { if (sex[i] -1 || sex[i] (B.female ? 1 : 0)) continue; if (fabs(affB[i] - bestB) EPS) { cout formatPerson(B.id, B.female) formatPerson(i, sex[i] 1) \n; } } } return 0; }4.2 几个必须注意的细节首先sex 数组是必须的。因为最后遍历编号 i 的时候要判断编号 i 这个人的性别光靠 affA 和 affB 数组无法知道每个人是男是女。所以读入照片时就要顺手记录每个人的性别。其次加亲密度的时候要小心“跳过自己”的判断。直接比较 id 还不够因为 A 可能是女 0 号而照片里可能还有一个男 0 号正常情况下题目数据不会这样安排但比较 id 和 female 双条件肯定更严谨代码里我也这么写了。第三中间变量 bestA 初始化为 -1.0而不是 0.0这样可以兼容所有异性亲密值都为 0 的边界情况。如果初始化为 0而 A 没有任何照片那么所有异性亲密值 0 都会被正确算作并列最高逻辑上没错但如果 A 有异性且亲密度为负不可能亲密度不会是负数。所以初始化为 -1.0 是最稳妥的。5. 其他高频踩坑点与排查速查5.1 并列最亲密漏输出很多人在收集候选时只保存第一个遇到的最大值遇到并列的就只输出一个。题目明确说了所有达到最高亲密度的异性都要输出。所以收集候选时不能只记一个下标要么用两遍遍历第一遍找最大值第二遍收集所有等于最大值的要么在遍历过程中不断更新最大值和候选容器。用浮点数比较时一定要注意精度直接比较 affA[i] bestA 有风险因为累加 1/K 的过程中会有浮点误差。建议统一用 fabs(affA[i] - bestA) EPS 判断。5.2 输出顺序错误候选输出的顺序必须按编号绝对值递增。因为正负号只表示性别编号本身的范围是 0 到 N-1所以从 0 到 N-1 遍历输出自然就是先按绝对值升序。如果自己额外排序反而容易把性别符号混进去导致顺序错乱。5.3 互选判断与输出分支互选判断的两个条件必须同时满足B 是 A 的最高异性之一且 A 是 B 的最高异性之一。这里要注意“最高异性之一”不是“唯一最高”。如果 A 的候选列表里有 3 个人其中包含 B那么 B 仍然算 A 的最高异性同理 B 的候选列表里也要包含 A才能输出互选那一行。互选成立后只输出一行A 的其他候选、B 的其他候选都不再输出。这个分支很多人都栽过因为样例往往只覆盖了不互选的情况。5.4 常见问题速查表症状原因解决办法测试点3 一直 WAID 用 int 读-0 性别丢失全部按字符串读手动解析符号本地测试全对提交就错输入了 -0 但代码没处理检查 parsePerson 和 formatPerson并列候选输出不全只用 比较浮点数使用 EPS 判断相等输出顺序不对自己排序时混入符号直接按 0 到 N-1 遍历互选后多输出几行分支逻辑写错互选成立立即输出一行并结束输出 -0 变成了 0格式化函数没处理 id0female 且 id0 时单独输出 -05.5 关于照片里 K1 的情况每张照片人数 K 最小是 1这时照片里只有一个人没有任何两个人之间的关系亲密度累加应该是 0。代码里 1.0 / photo.size() 得到 1.0但循环里除了自己之外没有其他人所以不会累加给任何人没问题。不要担心除零K 不会为 0。5.6 关于 A 和 B 可能是同性的情况题目并没有保证 A 和 B 一定是异性。如果 A 和 B 都是男性或者都是女性那么他们永远不可能是彼此的“最亲密异性”走的一定是“不互选”分支。代码里的互选判断已经考虑了性别条件所以这种情况也能正确输出。6. 一个测试点引出的边界测试思考6.1 -0 这种坑在测试用例里很常见其实 L2-028 的测试点3放在软件测试的语境里就是一个典型的边界值测试用例。它没有考你高深的算法而是考你会不会注意到“输入格式里的符号不仅代表数学正负还代表了业务语义”。这种思路和平时梳理登录模块的测试点很像。比如你用 XMind 梳理登录模块测试点的时候除了正常账号密码、错误账号密码还要单独列出“空字符串”“纯空格”“超长字符串”“密码前后带空格”“大小写混合”“全角半角符号”这些边界情况。它们看起来不复杂但一旦某个环节用类型转换直接吞掉了特殊字符整个校验逻辑就会出错。-0 被 int 读成 0本质上是“类型转换吞掉了业务信息”和“前端把空字符串转成 null”是一样的道理。6.2 做题和设计测试用例的态度是一致的刷这道题能刷出测试思维来永远不要默认输入是你最熟悉的那种“正常情况”。你要主动问自己输入表示里有没有可能被语言特性吞掉信息的地方输出格式里有没有可能产生歧义的边界把这些可能性提前在脑子里过一遍相当于在动手写代码之前就做了一轮思维层面的测试用例设计。如果你平时习惯用 XMind 梳理测试点那这道题其实也是一个很好的例子给“ID 解析”这个模块画一个分支一边是普通正数另一边是负数负数分支里一定要单独标出“-0”这个叶子节点。很多问题不是出在主干逻辑上而是出在这些不起眼的叶子节点上。最后说点个人体会。我被这道题教育过一次之后现在看到“用正负号表示属性”的输入第一反应永远是当字符串读永远不图省事直接用 int 接收。写完解析函数之后还会顺手写一个和原来输入相反的格式化输出函数保证解析和输出是对称的。这个习惯看起来多余但在很多题里都能救命。希望这篇能帮你把测试点3彻底弄明白顺利 AC。