高效统计「旗鼓相当的对手3」：排序+二分查找区间计数

我们来仔细分析这道题： --- ### 🔍 题目解析 - 有 `n` 名同学，每人有一个**战力成绩**（题目中写的是“战力成绩”，但描述里又说“数学成绩的分差”，结合样例，应统一理解为：每个学生有一个整数分数）。 - 定义一对学生 `<i, j>`（其中 `i < j`，隐含无序对，避免重复计数）是 **“旗鼓相当的对手3”**，当且仅当： $$ |a_i - a_j| \leq k $$ - 要求：统计满足条件的无序对 `<i, j>` 的总数。 ⚠️ 注意：题目中写的是“某对学生 `<i,j>`”，未说明是否有序；但输出是“对”的数量，且样例验证表明是**无序对（即 i < j）**，否则会重复计算。 --- ### 🧮 样例验证 输入： ``` 5 10 100 80 90 95 60 ``` 即：`n = 5`, `k = 10`, 分数数组 `a = [100, 80, 90, 95, 60]` 枚举所有 `i < j` 的组合（共 C(5,2)=10 对），计算 `|a[i]-a[j]| ≤ 10 ?` | i | j | a[i] | a[j] | diff | ≤10? | |---|---|------|------|------|------| | 0 | 1 | 100 | 80 | 20 | ❌ | | 0 | 2 | 100 | 90 | 10 | ✅ | | 0 | 3 | 100 | 95 | 5 | ✅ | | 0 | 4 | 100 | 60 | 40 | ❌ | | 1 | 2 | 80 | 90 | 10 | ✅ | | 1 | 3 | 80 | 95 | 15 | ❌ | | 1 | 4 | 80 | 60 | 20 | ❌ | | 2 | 3 | 90 | 95 | 5 | ✅ | | 2 | 4 | 90 | 60 | 30 | ❌ | | 3 | 4 | 95 | 60 | 35 | ❌ | ✅ 满足的有：`(0,2), (0,3), (1,2), (2,3)` → 共 **4 对**，与样例输出一致。 --- ### ⚙️ 解法选择 #### ✅ 方法一：暴力 O(n²)（适用于 n ≤ 10⁴ 左右） - 直接双重循环，枚举所有 `i < j`，判断 `abs(a[i] - a[j]) <= k` - 时间复杂度：O(n²)，空间 O(1) - 对于 `n ≤ 10^4`，最坏 1e8 次操作，在 Py/Java/C++ 中勉强可过（C++/Java 更稳，Python 可能卡常，但题目没给 n 上限？看提示） > 提示说：“对于100%的数据:” 后面没写……但通常这类题 `n ≤ 10^5`，此时 O(n²) 会超时（10¹⁰ 操作），需优化。 #### ✅ 方法二：排序 + 双指针 / 二分（推荐，O(n log n)） 思路： - 排序后，对每个 `a[i]`，找有多少 `a[j]`（j > i？不，排序打乱下标，但我们只关心值）满足 `a[i] ≤ a[j] ≤ a[i] + k` - 由于只关心**数值差**，且 `|a-b|≤k ⇔ a-k ≤ b ≤ a+k`，所以对每个 `a[i]`，在排序数组中查找区间 `[a[i]-k, a[i]+k]` 内的元素个数，再减去自身（或用二分找左右边界） 但注意：这样会把 `(i,j)` 和 `(j,i)` 都算一次（因为是值匹配），而我们需要的是**无序对个数**，即每对只算一次。所以我们应该： ✅ 正确做法（推荐）： - 排序数组 `a` - 使用**双指针（滑动窗口）** 或 **对每个左端点二分右边界**，统计满足 `a[j] - a[i] ≤ k` 且 `i < j` 的对数 （注意：排序后 `a[j] ≥ a[i]`，所以 `|a[i]-a[j]| = a[j]-a[i]`，只需保证 `a[j] ≤ a[i] + k`） 但注意：若直接对每个 `i` 找最大的 `j` 使得 `a[j] ≤ a[i] + k`，则区间 `[i+1, j]` 中所有 `k` 都满足 `a[k] - a[i] ≤ k`，且因已排序，自动满足 `a[k] ≥ a[i]` ⇒ `|diff| = a[k]-a[i]` ✅ 所以： - 排序后，对每个 `i`，用二分查找最大索引 `r`，使得 `a[r] ≤ a[i] + k` - 则对 `i` 贡献的对数为：`max(0, r - i)`（因为 `j` 必须 > i，且 `j ∈ [i+1, r]`） > ✅ 这样每对 `(i,j)`（i<j）被精确统计一次（按较小值 `a[i]` 作为左端点） ##### 示例验证（排序后）： 原数组：`[100, 80, 90, 95, 60]` 排序后：`[60, 80, 90, 95, 100]`，k=10 | i | a[i] | a[i]+k | r = rightmost index with a[r] ≤ a[i]+k | count += r - i | |---|------|--------|------------------------------------------|----------------| | 0 | 60 | 70 | a=[60,80,...] → only a[0]=60 ≤70 ⇒ r=0 | 0 - 0 = 0 | | 1 | 80 | 90 | a[2]=90 ≤90, a[3]=95>90 ⇒ r=2 | 2 - 1 = 1 | | 2 | 90 | 100 | a[4]=100 ≤100 ⇒ r=4 | 4 - 2 = 2 | | 3 | 95 | 105 | r=4 | 4 - 3 = 1 | | 4 | 100 | 110 | r=4 | 4 - 4 = 0 | | **sum** | | | | **0+1+2+1+0 = 4** ✅ | 完美匹配！ --- ### ✅ 最终算法（Python 实现） ```python import bisect n, k = map(int, input().split()) a = list(map(int, input().split())) a.sort() ans = 0 for i in range(n): # 找最大的 j，使得 a[j] <= a[i] + k # bisect_right 返回插入位置，即第一个 > a[i]+k 的位置 r = bisect.bisect_right(a, a[i] + k) # j must be > i, so valid indices: [i+1, r-1] → count = max(0, r - i - 1) # BUT WAIT! above manual table used r - i, but that counted j from i to r-1 inclusive? # Let's recheck definition: # bisect_right(a, x) = first index where a[idx] > x → elements ≤ x are a[0:r] # So indices j with a[j] ≤ a[i]+k are j in [0, r-1] # We need j > i → j in [i+1, r-1] → count = max(0, r - 1 - i) = r - i - 1 # But our manual table used r - i and got correct 4. Why? # Because in table we defined r as *inclusive* last index. # bisect_right returns exclusive upper bound → so number of elements ≤ x is r. # So j can be from i+1 to r-1 → count = r - (i+1) = r - i - 1. # Let's recalc table with this: # i=0: a[0]=60, x=70, a=[60,80,90,95,100], bisect_right=1 → r=1 → count = 1-0-1 = 0 ✅ # i=1: a[1]=80, x=90, a[2]=90≤90, a[3]=95>90 → bisect_right=3 → count=3-1-1=1 ✅ # i=2: a[2]=90, x=100 → bisect_right=5 → 5-2-1 = 2 ✅ # i=3: a[3]=95, x=105 → bisect_right=5 → 5-3-1 = 1 ✅ # i=4: 5-4-1 = 0 ✅ # sum = 4 → correct. ans += max(0, r - i - 1) print(ans) ``` ✅ 时间复杂度：O(n log n)，空间 O(1)（除输入存储） --- ### 🧩 边界注意事项 - `n` 可能为 0 或 1 → 输出 0 - `k` 可能为 0 → 只统计相等元素对（可用 `Counter` 优化，但当前方法仍适用） - 数值范围大（≤10⁹），但 Python `bisect` 支持，无问题 --- ### 💡 进阶优化（可选） - 若 `k=0`，可用哈希表统计频次，对每个频次 `c`，加 `c*(c-1)//2` - 若 `k` 很小，可考虑桶/基数排序，但一般没必要 --- ### ✅ 最终代码（简洁版） ```python import bisect n, k = map(int, input().split()) a = sorted(map(int, input().split())) ans = 0 for i in range(n): r = bisect.bisect_right(a, a[i] + k) ans += r - i - 1 print(ans) ``` --- ######[AI写代码神器 | 2588点数解答 | 2026-03-05 12:15:10]