求奶牛产奶量中位数：排序取索引 N//2 的经典算法实现

这道题是经典的**求中位数（Median）问题**，但需要注意题目中对中位数的定义： > “一半的奶牛产奶量 ≥ 中位数，一半的奶牛产奶量 ≤ 中位数” 并且给出了两个例子： - `N = 5` → 输出第 **3 小** 的数（即排序后索引为 `2`，0-indexed） - `N = 6` → 输出第 **4 小** 的数（即排序后索引为 `3`） 🔍 我们来验证这个规律： | N | 期望中位数位置（1-indexed） | 对应数组索引（0-indexed） | |---|-----------------------------|----------------------------| | 5 | 第 3 小 | `index = (5-1)//2 = 2` ✅ | | 6 | 第 4 小 | `index = 6//2 = 3` ✅ | 所以通用规则是： > 对于 `N` 个数，**中位数 = 排序后下标为 `N // 2` 的元素（0-indexed）** ✅ 这正是 **下中位数（lower median）** 的定义，在编程竞赛中常用于奇偶统一处理。 例如： - `N=5`: `5//2 = 2` → 第3个数（1-indexed） - `N=6`: `6//2 = 3` → 第4个数（1-indexed） --- ### ✅ 解法思路（高效可行，因 N 可达 1e6） - **方法1（推荐）：排序 + 取索引 `N//2`** - 时间复杂度：`O(N log N)`，对 `N ≤ 1e6` 完全可接受（Python 的 `sorted()` 在 CPython 中非常快） - **方法2（进阶）：快速选择算法（QuickSelect）** - 平均 `O(N)`，最坏 `O(N²)`，但实现稍复杂，本题无需 --- ### ✅ Python 实现（简洁、正确、通过样例） ```python n = int(input()) milk = list(map(int, input().split())) milk.sort() print(milk[n // 2]) ``` 📌 **说明：** - `n // 2` 是整数除法，Python 中 `5//2 == 2`, `6//2 == 3` - 排序后直接取中间偏右的那个（即第 `⌈n/2⌉` 小的数），满足题意“至少一半 ≥ 它，至少一半 ≤ 它” --- ### 🔍 验证样例： 输入： ``` 5 1 2 3 4 5 ``` → 排序后 `[1,2,3,4,5]`，`n//2 = 2` → `milk[2] = 3` ✅ 再试 `N=6`： ``` 6 1 2 3 4 5 6 ``` → 排序后 `[1,2,3,4,5,6]`，`6//2 = 3` → `milk[3] = 4` ✅ --- ### 💡 小贴士（开发建议）： - 若数据极大（如 N > 1e7）且内存受限，可考虑 **计数排序（Counting Sort）**，因为产奶量范围是 `1~1e6`，适合桶排序，时间复杂度 `O(max_value)`。 - 注意：Python 的 `sys.stdin` 在读大数据时比 `input()` 快很多，可用如下优化： ```python import sys n = int(sys.stdin.readline()) milk = list(map(int, sys.stdin.readline().split())) milk.sort() print(milk[n // 2]) ``` --- ######[AI写代码神器 | 884点数解答 | 2026-03-24 17:24:02]