APIO2007竞赛：最小交换次数使风铃符合Ike喜好

本题来源于2007年的亚太地区信息学奥林匹克竞赛APIO的试题，题目名为"风铃(Mobiles)"，主要考察参赛者对数据结构和算法设计的理解。题目背景是主人公需要为弟弟Ike选择一个能满足特定条件的风铃作为礼物，这个风铃需符合以下两个条件： 1. 玩具层次一致性：所有的玩具应处于同一层，或者最多相差一层。这意味着所有玩具到天花板的距离应该相同或最多只有一次差距。 2. 位置关系：对于相邻且相差一层的玩具，左侧的玩具必须低于右侧的玩具。 题目提供了输入文件mobiles.in和输出文件mobiles.out，给出了时间限制（1秒）和内存限制（32MB）。参赛者需要设计一个算法，判断如何通过重新排列风铃的杆子来满足Ike的喜好，并计算出最少需要进行多少次杆子的“交换”操作。输入描述中提到，每行包含两个整数，li和ri，分别代表杆i的左右两端所挂的物品。如果是一个玩具，li和ri将是-1；如果是挂有其他杆子，那么这两个值将对应下方杆子的编号，且编号大于i。 解题的关键在于构建一个树形数据结构来表示风铃，每个杆子代表一个节点，根据li和ri的关系建立父子关系。然后，通过递归或深度优先搜索遍历这个结构，找出玩具的正确层次并调整位置关系。为了找到最小的交换次数，可以使用回溯法或者动态规划策略，尝试不同的排列顺序，每次交换后检查是否满足条件，记录下最少的交换次数。 此题要求参赛者运用图论、树状数据结构以及优化算法的思想，解决实际问题，同时考虑性能和效率，因为时间限制非常严格。通过解决这个问题，参赛者不仅锻炼了解决实际问题的能力，还加深了对数据结构和算法核心概念的理解。