第1课 金块问题(gold)-2020.04.18).pdf

### 金块问题详解 #### 一、问题背景与描述 **标题与描述**：“第1课 金块问题(gold)-2020.04.18).pdf” 提示了本节课程的主题是关于如何高效地解决金块问题。金块问题的核心在于寻找一组金块中的最重和最轻的金块，并且尽量减少比较的次数。 **标签**：“NOIP 信奥 分治” 表明这是一个针对全国青少年信息学奥林匹克联赛(NOIP)的训练题目，采用了“分治”这一算法思想。 #### 二、问题定义与分析 **问题描述**：一位老板有一袋包含n块金子的袋子，每月需要选出最重和最轻的两块金子作为奖励。问题的目标是在最少的比较次数下确定这两块金子的重量。 **输入格式**：第一行包含一个整数n (2 ≤ n ≤ 100000)，代表金块的数量；第二行包含n个整数，表示每块金子的重量。 **输出格式**：输出两个整数，即最重和最轻的金块的重量。 #### 三、传统解决方案分析 文档中提出了两种传统的方法： 1. **直接比较法**：遍历所有金块，逐一比较，以找到最重和最轻的金块。这种方法的时间复杂度为 O(n)。具体来说，每次循环需要两次比较操作，总共需要 2n - 2 次比较。 ```cpp maxa = mina = a[1]; for (int i = 2; i <= n; ++i) { if (a[i] > maxa) maxa = a[i]; if (a[i] < mina) mina = a[i]; } ``` 2. **两步比较法**：首先通过 n - 1 次比较找到最重的金块，然后将它移除，并在剩余的 n - 1 块金块中通过 n - 2 次比较找到最轻的金块。总比较次数为 2n - 3。 ```cpp maxa = a[1]; for (int i = 2; i <= n; ++i) { if (a[i] > maxa) { maxa = a[i]; j = i; } } swap(a[j], a[n]); mina = a[1]; for (int i = 2; i < n; ++i) { if (a[i] < mina) mina = a[i]; } ``` 这两种方法虽然有效，但都未能达到最优的比较次数。 #### 四、分治法求解 **分治法原理**：分治法的基本思想是将大问题分解成若干个规模较小但结构相同的小问题，递归地解决这些子问题，最后将子问题的解合并成原问题的解。 **分治步骤**： 1. **分解(divide)**：将原问题分成一系列子问题。 2. **解决(conquer)**：递归地解各子问题。若子问题足够小，则可以直接求解。 3. **合并(combine)**：将子问题的结果合并成原问题的解。 **具体过程**：使用分治策略通常涉及递归结构。以二分法为例，可以将金块分成两组，分别求解每组的最重和最轻的金块，然后再进行比较，以获得最终答案。 **算法实现**：以下是一个基于分治法求解金块问题的伪代码示例： ```cpp void findMinMax(int a[], int start, int end, int& min, int& max) { if (start == end) { // 只有一个元素的情况 min = max = a[start]; } else if (end - start == 1) { // 只有两个元素的情况 if (a[start] < a[end]) { min = a[start]; max = a[end]; } else { min = a[end]; max = a[start]; } } else { // 一般情况 int mid = (start + end) / 2; int lmin, lmax, rmin, rmax; findMinMax(a, start, mid, lmin, lmax); findMinMax(a, mid + 1, end, rmin, rmax); min = min(lmin, rmin); max = max(lmax, rmax); } } ``` 此算法的时间复杂度接近于 O(n)，但相比直接比较法减少了不必要的比较次数。例如，在 n = 8 的情况下，直接比较法需要 14 次比较，而分治法则只需要 13 次比较，随着 n 的增大，节省的比例会更加显著。