Problem J43: Gold Bar Distribution / 金块问题

版权信息： · 分治法题目

任务总览

题目描述

某公司老板拥有一袋金块，其中有 $n$ 块金子。每个月老板会根据员工表现，选出两名员工发放金块作为奖励：

• 第 $1$ 名员工会得到 ​ 袋中最重的金块 ​；
• 第 $2$ 名员工会得到 ​ 袋中最轻的金块 ​。

为了公平分发，每个月都需要找到当前袋中 最重 与 最轻 的金块。

你有一台仪器，可以比较任意两块金子的重量。现在希望你通过最少的比较次数，找出这袋金块中质量 最重 和 最轻 的金块。

输入格式

*第 $1$ 行：一个正整数 $n$（$2 \leq n \leq 10 ^ 5$），表示金块的数量；

• 第 $2$ 行：$n$ 个正整数，表示每块金子的质量（整数不超过 $10 ^ 9$）。

输出格式

输出两个用空格分隔的整数，依次表示袋中金块的 最大质量 和 ​ 最小质量 ​。

输入输出样例

输入示例

7
8 7 5 6 9 4 5

输出示例

9 4

题目分析与解法

✅ 方法一：顺序扫描（选择排序思想）

直接遍历一遍数组，记录当前最小值和最大值：

• 时间复杂度：$O(n)$；
• 比较次数：$2(n - 1)$。

✅ 方法二：分治法（减少比较次数）

• 将数组分成两半，递归查找每一半的最大最小值；
• 最终将子问题结果合并；
• 时间复杂度仍是 $O(n)$，但​ 平均比较次数少于顺序扫描法 ​；
• 是典型的分治法应用。

时间复杂度分析