1. 项目概述从一道信奥题看算法竞赛的实战思维最近在带学生刷信奥信息学奥林匹克的题目碰到了一个挺有意思的题P10710 [NOISG 2024 Prelim] School Photo。这道题来自新加坡国家信息学奥林匹克竞赛NOI Singapore2024年的预选赛题目名字叫“班级合影”听起来挺生活化但内核却是一个典型的组合优化与贪心算法问题。很多刚接触信奥的同学一看到“合影”、“排队”这类描述容易下意识地往模拟题去想结果一上手就发现数据规模巨大暴力枚举根本过不了。这正是信奥题目的魅力所在——它用一个贴近生活的场景包装了一个需要你深入思考算法本质的问题。这道题的核心是要求我们为N个身高不同的学生排成两排合影使得最终形成的“不和谐度”总和最小。这里的不和谐度通常定义为同一列中后排学生比前排学生高的“对数”。换句话说我们要找到一种排列方式让后排挡住前排的情况尽可能少。这立刻就把问题从“怎么排”提升到了“怎么最优地排”的层面。在信奥赛场上尤其是NOI Singapore这种级别的比赛题目绝不会止步于让你写一个O(N!)的穷举程序它考验的是你对贪心策略的证明能力、对数据结构的灵活运用以及将实际问题抽象为数学模型的功力。我之所以选择用C来实现它一方面是因为C是信奥竞赛的官方语言其执行效率和对底层内存的控制能力是处理大规模数据比如N最大可能到10^5的保障。另一方面通过这道题我们可以串联起很多C在竞赛中的核心技巧比如如何使用vector和pair来高效存储和处理数据如何利用sort函数配合自定义比较器来实现复杂的排序逻辑以及如何设计算法将时间复杂度从指数级降低到O(N log N)甚至O(N)。接下来我就把自己拆解和实现这道题的完整思路、踩过的坑以及优化技巧毫无保留地分享给大家。2. 问题解析与数学模型建立2.1 题意重述与关键约束首先我们必须把题目描述从“生活语言”精确地翻译成“算法语言”。题目“School Photo”通常包含以下要素学生共有N个学生每个学生有一个唯一的身高值height[i]。为简化问题我们通常假设身高两两不同这在竞赛题中很常见。队列形式学生需要排成两排每排恰好有N/2个人这里假设N是偶数奇数情况可能有特殊处理但题目一般会说明。前排和后排的学生一一对齐形成N/2列。不和谐度定义对于每一列如果后排学生的身高大于前排学生的身高则认为这一列产生了1点“不和谐度”。总不和谐度就是所有列的不和谐度之和。目标找到一种将学生分配到前排和后排并为每排学生确定顺序的方案使得总不和谐度最小。这里有一个非常重要的隐含约束学生一旦被分配到前排或后排他在该排内部的顺序是可以任意调整的。这给了我们优化的空间。如果我们先固定了分配方案即确定哪些人去前排哪些人去后排那么对于每一排内部我们可以自由排序以进一步降低不和谐度。2.2 贪心策略的直觉与初步分析面对这样一个优化问题我们的第一反应是能不能用贪心算法贪心的核心是“每一步都做出当前看起来最优的选择”。对于这道题一个强烈的直觉是应该让身高相近的学生站在同一列。因为如果一列中前后排身高差距很大那么后排比前排高的概率或者说为了降低不和谐度而被迫做出的排序代价就会增大。更进一步的思考是如果我们已经将所有学生按身高从低到高排序那么一个自然的想法是将排序后的学生按顺序交替分配到前排和后排。例如身高最小的给前排次小的给后排第三小的给前排第四小的给后排……以此类推。这样每一列配对时比如前排第i个和后排第i个他们的身高在全局序列中是相邻的差距最小。但这个策略对吗我们需要更严谨的分析。假设我们采用这种“交错分配”法那么前排的学生将占据排序后序列的所有奇数位第135...高后排则占据偶数位第246...高。接下来为了最小化不和谐度对于已经分配好的前排和后排我们各自按身高升序排列。那么在最终一一对应的列中前排第i高的人对应的是全局第(2i-1)高的人后排第i高的人对应的是全局第(2i)高的人。由于序列是升序的必然有前排[i] 后排[i]因为2i-1 2i。这意味着每一列的后排都比前排高不和谐度达到了最大值N/2这显然不是我们想要的结果。这个反例告诉我们简单的“交错分配”是行不通的。我们需要更优的贪心策略。2.3 最优策略的推导与证明正确的思路需要转换视角。我们考虑最终的状态当两排都按身高升序排列好后总不和谐度是多少设前排升序序列为F1, F2, ..., Fk后排升序序列为B1, B2, ..., Bk其中kN/2。不和谐度就是满足Bi Fi的i的个数。一个关键的观察是我们可以将问题转化为一个匹配问题。将排序后的全体学生升序序列S平均分成前后两半是否是一种更好的分配方式我们来验证一下策略将排序后的学生前一半较矮的N/2个分配到后排后一半较高的N/2个分配到前排。排序分配好后前排较高的一半自身按身高升序排列后排较矮的一半也按身高升序排列。结果分析此时对于任何一列i我们有Fi来自较高的那一半Bi来自较矮的那一半。因此必然有Fi Bi。这意味着没有一列会产生不和谐度总不和谐度为0。这听起来太完美了但这里有一个陷阱题目允许我们自由排列每排内部的顺序。在上面的策略中我们让前排全高于后排固然得到了0不和谐度但这真的是题目所求吗仔细读题“不和谐度”定义为后排比前排高。如果前排比后排高是不算不和谐度的。所以让前排全部最高后排全部最矮确实可以得到理论上的最小值0。然而这是否是唯一的解或者说这是否是题目期望的答案在实际的竞赛题中往往会有额外的条件或约束比如“合影要美观”可能隐含了身高不能相差太大的要求或者题目定义的“不和谐度”是绝对身高差等其他度量。但在经典的“最小化后排高于前排的对数”问题中将较高的学生放在前排较矮的学生放在后排并各自按升序排列确实是唯一的最优策略且最优值为0。但让我们再思考一个更一般化也更常见的问题变种如果目标是最小化|Bi - Fi|身高差的绝对值的总和或者是最小化max(Bi, Fi)每列最高者的总和呢这时策略就完全不同了。这也提醒我们严格建模是第一步。对于P10710这道题根据其过往的赛题风格和“School Photo”的常见出题方式我强烈推测它的目标就是最小化“后排高于前排”的列数那么上述“前矮后高”的策略就是核心。注意在实际操作中务必通过题目给出的样例输入输出来验证你的策略。如果样例都过不了说明要么策略错了要么你对题意的理解有偏差。这是信奥答题的金科玉律。3. C实现详解与代码拆解在确定了“将身高排序后的前N/2小放到后排并升序排列后N/2大放到前排并升序排列”这一核心策略后接下来的任务就是用C高效且正确地实现它。这个过程涉及输入处理、数据排序、分配逻辑和输出格式每一个环节都有需要注意的细节。3.1 数据结构设计与输入处理首先我们需要存储N个学生的身高。由于N可能很大10^5量级我们选择使用std::vectorint来动态存储这不仅方便而且内存连续访问效率高。#include iostream #include vector #include algorithm // 用于sort函数 using namespace std; int main() { int N; cin N; vectorint heights(N); for (int i 0; i N; i) { cin heights[i]; } // ... 后续处理 }这里有一个实操心得在竞赛中关闭C标准输入输出流与C标准输入输出流的同步可以显著提升大量数据读入的速度。我们可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);这样处理之后cin和cout的速度会接近C语言的scanf和printf但要注意一旦使用了这行代码就不能再混用printf/scanf和cout/cin否则会导致输出顺序错乱。3.2 核心算法步骤实现接下来是算法的核心部分我们分步实现步骤1对全体身高进行排序sort(heights.begin(), heights.end());std::sort默认是升序排列时间复杂度为O(N log N)完全满足要求。步骤2分配前后排并排序根据我们的策略前排应取排序后较大的那一半后排取较小的那一半。但这里有一个关键点取出来之后前排和后排各自也需要是升序的这样在最终输出时同一排的学生身高是从左到右递增的符合“合影”的直观感受。int k N / 2; // 每排的人数 vectorint front_row(k), back_row(k); // 分配后排取前k个较矮的前排取后k个较高的 for (int i 0; i k; i) { back_row[i] heights[i]; // 较矮的给后排 front_row[i] heights[i k]; // 较高的给前排 } // 虽然heights已经有序但back_row和front_row本身也是有序的 // 因为heights是升序所以back_rowheights[0..k-1]自然升序 // front_rowheights[k..2k-1]也自然升序 // 所以理论上不需要再次排序。但为了逻辑清晰我们可以显式排序对性能影响极小。 // sort(back_row.begin(), back_row.end()); // sort(front_row.begin(), front_row.end());实际上由于源数组heights是升序的我们按顺序赋值给back_row和front_row后这两个数组自然就是升序的不需要再次调用sort。这是一个可以省略但无伤大雅的步骤。步骤3计算不和谐度可选根据我们的策略front_row[i]永远大于back_row[i]所以不和谐度为0。如果题目要求输出这个值直接输出0即可。int discomfort 0; for (int i 0; i k; i) { if (back_row[i] front_row[i]) { // 根据我们的分配这永远不会成立 discomfort; } } cout discomfort endl; // 输出0步骤4输出排列方案题目很可能要求输出具体的排列方案即前排的顺序和后排的顺序。// 输出前排 for (int i 0; i k; i) { cout front_row[i]; if (i ! k - 1) cout ; // 最后一个数字后不加空格 } cout endl; // 输出后排 for (int i 0; i k; i) { cout back_row[i]; if (i ! k - 1) cout ; } cout endl;重要提示输出格式是信奥题目中最常见的失分点之一。务必严格按照题目要求输出注意空格和换行。比如这里每排内数字用空格隔开行末不能有多余空格。上面if (i ! k - 1)的判断就是为了处理这个细节。3.3 完整代码整合与测试将以上所有部分整合起来并加上必要的注释就得到了完整的解决方案#include iostream #include vector #include algorithm using namespace std; int main() { // 加速输入输出 ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorint heights(N); for (int i 0; i N; i) { cin heights[i]; } // 1. 按身高升序排序 sort(heights.begin(), heights.end()); int k N / 2; vectorint front_row(k), back_row(k); // 2. 分配较矮的一半给后排较高的一半给前排 for (int i 0; i k; i) { back_row[i] heights[i]; // 后排较矮者 front_row[i] heights[i k]; // 前排较高者 } // 此时 front_row 和 back_row 内部已经是有序的 // 3. 计算不和谐度理论上为0 int discomfort 0; for (int i 0; i k; i) { if (back_row[i] front_row[i]) { discomfort; } } // 输出不和谐度 cout discomfort endl; // 4. 输出前排顺序 for (int i 0; i k; i) { cout front_row[i]; if (i ! k - 1) cout ; } cout endl; // 5. 输出后排顺序 for (int i 0; i k; i) { cout back_row[i]; if (i ! k - 1) cout ; } cout endl; return 0; }4. 算法正确性证明与复杂度分析对于一个竞赛题解除了给出代码还需要向评委或者自己证明它为什么是对的以及它为什么足够快。4.1 贪心策略正确性证明我们声称上述策略能得到最优解不和谐度为0。证明如下定义设总学生集合S已按升序排列为{s1, s2, ..., sN}其中s1 s2 ... sN。目标将S分成两个大小均为kN/2的子集F前排和B后排并确定各自内部的排列顺序最小化|{i: B_i F_i}|。其中F_i和B_i是两排排好序后第i列的学生。关键引理在最优解中两排各自内部一定按身高升序排列。为什么假设在某排中存在逆序即高个站在矮个左边那么交换这两个人的位置不会影响他们与另一排的对应关系因为列的顺序没变但可能使得本排更有序。对于最小化“后排高于前排”的目标让前排尽可能高、后排尽可能矮总是有益的而升序排列是让前排“显得更高”、后排“显得更矮”的一种方式在固定集合下。更严格地说如果前排不是升序我们可以通过交换使其变成升序这个过程不会增加任何一列的不和谐度可能减少或不变。后排同理。因此存在一个最优解其中两排各自都是升序的。基于引理的简化既然两排各自升序是最优的那么问题简化为如何将S划分成两个大小均为k的多重集F和B使得当F和B分别升序后满足B_i F_i的i尽可能少。最优划分考虑排序后的S。如果我们希望没有一列满足B_i F_i即希望所有列都满足F_i B_i。由于两排都是升序这意味着对于所有的iF_i必须大于等于B_i。最自然的保证方式就是让F中的所有元素都大于等于B中的所有元素。那么在排序序列S中直接取后k个作为F前k个作为B就满足了F中每个元素 B中每个元素。当各自升序后必然有F_i B_i对所有i成立不和谐度为0。结论上述划分方案是可行的并且达到了理论下界0因此它是最优解。这个证明过程体现了竞赛思维先简化问题证明最优解具有某种性质再在简化后的问题中寻找最优解。4.2 时间与空间复杂度分析时间复杂度整个算法的瓶颈在于对N个身高进行排序使用的是std::sort其平均和最坏情况时间复杂度为O(N log N)。后续的分配和输出都是O(N)的线性操作。因此总时间复杂度为O(N log N)对于N最大为10^5甚至10^6的数据规模都完全可行。空间复杂度我们使用了三个vectorintheights(大小N)、front_row(大小N/2)、back_row(大小N/2)。因此总空间复杂度为O(N)主要是存储输入数据和结果这在题目限制内是标准的。5. 常见问题与调试技巧实录即便思路清晰在实现和调试过程中尤其是竞赛环境下还是会遇到各种问题。下面是我和学生们在解决这类问题时经常遇到的坑和解决技巧。5.1 边界条件与特殊输入处理N为奇数怎么办题目描述中通常会说“两排每排人数相等”这暗示了N是偶数。但如果题目没有明确说明或者样例中有奇数我们就必须处理。对于奇数N常见的处理方式是让其中一排多一个人比如前排多一个。这时我们的分配策略需要调整排序后可以将中间那个身高中位数单独考虑或者采用其他策略。在动手前务必仔细阅读数据范围的说明这是习惯问题。实操心得在写代码前先在心里或纸上过一遍N1 N2 N3如果是奇数的情况确保逻辑不会崩溃。例如如果N1kN/2在整数除法下是0会导致创建大小为0的vector后续循环也可能出错。虽然信奥题通常不会给这么小的边界但养成检查的习惯能避免很多低级错误。身高有重复怎么办题目中“身高不同”是一个很强的简化条件。如果身高可以相同那么“不和谐度”的定义后排高于前排中“高于”是严格大于还是大于等于这会影响策略。如果允许相等那么我们的策略依然有效因为将较高的或相等中偏高的放到前排依然可以保证F_i B_i不和谐度为0。但输出时可能会有多种最优解。一定要看清题目的比较符号是还是。5.2 输入输出效率与格式错误大数据量下的超时TLE这是新手最常见的错误之一。如果你使用了cin/cout而没有关闭同步流或者使用了endl它会强制刷新缓冲区在输入输出数据量很大时比如10^5个数字速度会慢得惊人。解决方案使用ios::sync_with_stdio(false); cin.tie(nullptr);。用\n代替endl来换行。如果还是超时可以考虑用printf和scanf但要注意数据类型匹配%d对应int%lld对应long long。输出格式错误Presentation Error信奥评测系统对输出格式要求极其严格。多一个空格、少一个换行都会导致“格式错误”。解决方案像前面代码展示的那样在循环内输出数字和空格通过判断i ! k-1来避免行末空格。输出完成后检查是否按要求输出了换行。通常每个测试用例的输出都以换行结束。可以先用题目给的样例自己跑一遍把输出复制到文本编辑器里开启“显示空格和制表符”功能肉眼检查一遍。5.3 算法思维陷阱误解题意追求“对称”或“美观”这是“School Photo”类题目最经典的陷阱。生活中的合影我们可能希望前后排身高交错或者每列身高差最小。但竞赛题的目标函数是明确写出的“最小化后排高于前排的列数”。一定要忠于题目给出的数学定义而不是生活经验。我们的算法证明了让前排全部最高、后排全部最矮就能让这个目标函数值达到最小0。虽然拍出来可能前排像一堵墙挡住了后排但从算法角度看这是完美的。试图使用更复杂的算法有同学可能会想这是不是一种“二分图匹配”或者“动态规划”问题对于更复杂的目标函数比如最小化身高差之和可能需要DP。但对于本题的特定目标贪心已经足够且被证明是最优的。在竞赛中能用一个简单清晰的O(N log N)贪心解决的问题绝对不要用O(N^2)的DP去折腾。这考验的是对问题本质的洞察力。5.4 调试与测试策略构造小规模测试数据自己编一些小的测试用例比如N4身高为[1,2,3,4]或[4,3,2,1]手动计算预期输出再与程序输出对比。这是验证算法逻辑最基本有效的方法。对拍Diff Test当你不确定自己的算法是否正确时可以写一个“暴力枚举”的程序对于小N比如N10枚举所有可能的分配和排列方式计算目标函数找出真正的最优解。然后用你的“高效算法”去跑同样的随机小数据对比结果是否一致。这是信奥备赛时验证正确性的黄金手段。使用调试输出在代码关键步骤插入一些输出比如排序后的数组、分配后的前后排数组。这能帮你直观地看到数据是如何流动的快速定位逻辑错误。这道“打卡信奥刷题”的P10710题目从理解题意、数学建模、贪心证明到C实现完整地走完了一个竞赛题目的解决流程。它不像一些复杂的图论或数据结构题那样需要深厚的模板积累但非常考验选手的逻辑思维、问题转化和严谨性。真正理解了这道题你收获的不仅仅是一个AC代码更是一种面对优化类问题的通用思考方式先简化再观察提出猜想最后严谨证明或验证。在信奥的道路上这种思维能力的锻炼远比记住十个八个算法模板重要得多。下次再看到“合影”、“排队”、“分组”这类题目不妨先想想它的最优解结构是不是也有这样简洁优美的性质。