桶计数高效解法：统计“旗鼓相当的对手2”数对

这是一个经典的**数组中满足条件的数对计数问题**，要求统计所有满足 `|a[i] - a[j]| <= 10` 且 `i < j` 的无序对 `<i, j>` 的数量。 --- ### 🔍 题目分析 - 输入：`N ≤ 10⁵` 名学生，每人一个数学成绩 `a_i ∈ [0, 150]`（自然数，≤150） - 条件：“旗鼓相当的对手2” ⇔ `|a_i - a_j| ≤ 10` - 注意：是**无序对**，即 `<i,j>` 和 `<j,i>` 算同一个，且 `i ≠ j`；通常我们只统计 `i < j` 的情况。 ⚠️ **暴力 O(N²) 不可取**：`N = 10⁵ ⇒ N² = 10¹⁰`，超时！ ✅ 但注意关键约束：**成绩范围很小！最多 0~150（共 151 个不同值）** → 可以用**桶计数 + 枚举分数区间**优化到 `O(151 × 21) ≈ O(3171)`，非常高效！ --- ### ✅ 解法思路（推荐：桶计数 + 前缀和 / 直接枚举） #### 🧠 核心观察： - 成绩 `a_i ∈ [0, 150]` → 最多 151 种可能值。 - 对每个成绩 `x`，它能和成绩在 `[x−10, x+10] ∩ [0,150]` 内的所有其他成绩组成合法对。 - 若用 `cnt[x]` 表示成绩为 `x` 的人数，则： - 同分对数（`x == y`）：`C(cnt[x], 2) = cnt[x] * (cnt[x]-1) // 2` - 跨分对数（`x < y`）：`cnt[x] * cnt[y]`，其中 `y ∈ [x+1, x+10]`（避免重复） 所以我们只需： 1. 统计每个分数出现次数（桶数组 `cnt[0..150]`） 2. 枚举每个分数 `x`（0 到 150），对每个 `y ∈ [x, min(150, x+10)]`： - 若 `x == y`：加 `C(cnt[x], 2)` - 若 `x < y`：加 `cnt[x] * cnt[y]` > ✅ 时间复杂度：`O(151 × 11) = O(1661)`，极致高效！ --- ### 💻 Python 实现（清晰易懂） ```python N = int(input()) scores = list(map(int, input().split())) # 桶计数：cnt[s] = 分数 s 出现的次数（s ∈ [0, 150]） cnt = [0] * 151 # 索引 0 ~ 150 for s in scores: if 0 <= s <= 150: cnt[s] += 1 ans = 0 # 枚举每个基础分数 x for x in range(151): if cnt[x] == 0: continue # y ∈ [x, x+10] ∩ [0,150] left, right = x, min(150, x + 10) for y in range(left, right + 1): if cnt[y] == 0: continue if x == y: # 同分：组合数 C(cnt[x], 2) ans += cnt[x] * (cnt[x] - 1) // 2 else: # x < y：每对 x 和 y 学生都构成一对 ans += cnt[x] * cnt[y] print(ans) ``` --- ### ✅ 验证样例 输入： ``` 5 100 80 90 95 60 ``` 分数分布： - `cnt[60]=1`, `cnt[80]=1`, `cnt[90]=1`, `cnt[95]=1`, `cnt[100]=1` 检查所有 `(x,y)` 满足 `y ∈ [x, x+10]`： | x | valid y range | pairs contributed | |----|-------------------|-----------------------------------------| | 60 | [60,70] | only y=60 → C(1,2)=0 | | 80 | [80,90] | y=80→0; y=90→1×1=1 | | 90 | [90,100] | y=90→0; y=95→1; y=100→1 | | 95 | [95,105] → [95,100] | y=95→0; y=100→1 | |100 | [100,110] → [100] | y=100→0 | 总计：`1 + 1 + 1 + 1 = 4` ✅ （具体对：`(80,90)`, `(90,95)`, `(90,100)`, `(95,100)`） --- ### ⚙️ 进阶优化（可选） - 使用前缀和快速求区间 `sum(cnt[y])`，再配合 `cnt[x]` 计算跨分对数（但因范围极小，没必要）。 - 若成绩范围变大（如 0~10⁹），则需排序 + 双指针 / 二分查找，时间 `O(N log N)`。 --- ### 📌 开发建议 - **边界处理**：确保 `x+10` 不越界（`min(150, x+10)`） - **数据类型**：`cnt[x]` 最大为 `10⁵`，`cnt[x]*cnt[y]` 最大 `10¹⁰` → Python `int` 无压力，C++/Java 用 `long long` / `long` - **去重逻辑**：只枚举 `x ≤ y`，自然避免重复计数 - **测试用例补充**： - 全同分：`[90,90,90]` → `C(3,2)=3` - 无合法对：`[0, 100]` → 0 --- ######[AI写代码神器 | 1557点数解答 | 2026-03-05 12:18:57]