H. 樱子的测试 - 详细题解

问题重述

给定一个长度为 $n$ 的数组 $a$，可以进行任意次操作：选择 $a_i \ge x$ 的元素，将其减去 $x$。对于每个询问的 $x$，求操作后数组可能的最小中位数。

---

关键观察

观察 1：操作的效果

对于固定的 $x$，反复执行 $a_i = a_i - x$（当 $a_i \ge x$ 时）相当于：

$$a_i \to a_i \bmod x$$

因为我们可以不断减去 $x$ 直到 $a_i < x$。

因此，最终数组中的每个元素都变为 $a_i \bmod x$，取值范围为 $[0, x-1]$。

---

观察 2：最小化中位数

为了最小化中位数，我们希望尽可能多的元素变小。

由于最终值只能是 $0$ 到 $x-1$，我们无法改变模运算的结果，因此中位数的最小值就是最终数组的中位数。

---

观察 3：判断某个数 $m$ 是否可以是中位数

中位数定义为排序后第 $\lfloor n/2 \rfloor$ 个元素（$0$-based 索引）。对于偶数 $n$，取第 $\frac{n+2}{2}$ 个位置（$1$-based），等价于 $0$-based 索引 $\frac{n}{2}$。

设 $target = \lfloor n/2 \rfloor$（$0$-based）。

如果中位数 $\le m$，则至少需要 $target+1$ 个元素 $\le m$。

因此，我们需要计算有多少个 $i$ 满足 $a_i \bmod x \le m$。

---

观察 4：计算满足条件的元素个数

对于固定的 $x$ 和 $m$，$a_i \bmod x \le m$ 等价于存在整数 $k \ge 0$ 使得：

$$k \cdot x \le a_i \le k \cdot x + m$$

因为 $a_i$ 的范围是 $[1, n]$，所以 $k$ 的范围是 $0 \le k \le \lfloor n/x \rfloor$。

因此，满足条件的元素个数为：

$$cnt = \sum_{k=0}^{\lfloor n/x \rfloor} \text{count}(k \cdot x, k \cdot x + m) $$

其中 $\text{count}(l, r)$ 表示原数组中值在 $[l, r]$ 内的元素个数。

---

观察 5：预处理计数数组

由于 $a_i \le n$，我们可以构建一个计数数组 $freq[v]$ 表示值为 $v$ 的元素个数，然后计算前缀和：

$$pref[i] = \sum_{v=1}^{i} freq[v]$$

则 $\text{count}(l, r) = pref[r] - pref[l-1]$（当 $l \le r$ 时）。

---

观察 6：二分查找最小中位数

对于固定的 $x$，我们可以二分查找最小的 $m$ 使得满足条件的元素个数 $\ge target+1$。

二分范围：$[0, x-1]$。

检查函数 $check(m)$：计算 $cnt$ 并与 $target+1$ 比较。

---

观察 7：预处理所有 $x$

由于 $1 \le x \le n$，且 $n$ 的总和不超过 $10^5$，我们可以预处理所有 $x$ 的答案。

时间复杂度分析：

对于每个 $x$，需要遍历 $k = 0$ 到 $\lfloor n/x \rfloor$，共 $O(n/x)$ 个区间。二分查找需要 $O(\log x)$ 次检查。

因此总复杂度：

$$\sum_{x=1}^{n} \frac{n}{x} \cdot \log n \approx n \log n \cdot \sum_{x=1}^{n} \frac{1}{x} = n \log n \cdot H_n \approx n \log^2 n $$

由于 $\sum n \le 10^5$，$n \log^2 n \approx 10^5 \times 17^2 \approx 2.89 \times 10^7$，可以接受。

---

算法步骤

1. 读入 $n, q$ 和数组 $a$
2. 构建计数数组 $c$，并计算前缀和
3. 对于每个 $x$ 从 $1$ 到 $n$：
   • 二分查找最小的 $m$（$0 \le m < x$）使得满足 $a_i \bmod x \le m$ 的元素个数 $\ge \lfloor n/2 \rfloor + 1$
   • 将结果存入 $res[x]$
4. 对于每个查询 $x$，输出 $res[x]$

---

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, q;
        cin >> n >> q;
        
        vector<int> a(n);
        vector<int> cnt(n + 1, 0);
        
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            cnt[a[i]]++;
        }
        
        // 前缀和
        for (int i = 1; i <= n; i++) {
            cnt[i] += cnt[i - 1];
        }
        
        int target = n / 2;  // 0-based 中位数索引
        
        vector<int> res(n + 1, 0);
        
        // 预处理所有 x
        for (int x = 1; x <= n; x++) {
            int l = 0, r = x;
            
            while (l < r) {
                int mid = (l + r) / 2;
                
                // 计算有多少个元素 mod x <= mid
                int total = cnt[mid];  // k = 0 的情况
                
                for (int k = 1; k * x <= n; k++) {
                    int left = k * x;
                    int right = min(k * x + mid, n);
                    total += cnt[right] - cnt[left - 1];
                }
                
                if (total - 1 >= target) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            
            res[x] = l;
        }
        
        // 处理查询
        while (q--) {
            int x;
            cin >> x;
            cout << res[x] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

---

示例验证

测试用例 1

$n = 5, a = [1, 2, 3, 4, 5]$，$target = 5/2 = 2$

• $x = 1$：$a_i \bmod 1 = 0$，所有元素变为 $0$，中位数 $0$
• $x = 2$：$a_i \bmod 2 = [1, 0, 1, 0, 1]$，排序后 $[0, 0, 1, 1, 1]$，中位数 $1$
• $x = 3$：$a_i \bmod 3 = [1, 2, 0, 1, 2]$，排序后 $[0, 1, 1, 2, 2]$，中位数 $1$
• $x = 4$：$a_i \bmod 4 = [1, 2, 3, 0, 1]$，排序后 $[0, 1, 1, 2, 3]$，中位数 $1$
• $x = 5$：$a_i \bmod 5 = [1, 2, 3, 4, 0]$，排序后 $[0, 1, 2, 3, 4]$，中位数 $2$

输出：0 1 1 1 2 ✓

---

测试用例 2

$n = 6, a = [1, 2, 6, 4, 1, 3]$，$target = 6/2 = 3$

• $x = 2$：$a_i \bmod 2 = [1, 0, 0, 0, 1, 1]$，排序后 $[0, 0, 0, 1, 1, 1]$，中位数 $1$
• $x = 1$：所有元素变为 $0$，中位数 $0$
• $x = 5$：$a_i \bmod 5 = [1, 2, 1, 4, 1, 3]$，排序后 $[1, 1, 1, 2, 3, 4]$，中位数 $2$

输出：1 0 2 ✓

---

时间复杂度

• 预处理：$O(n \log^2 n)$
• 每个查询：$O(1)$
• 总复杂度：$O(\sum n \log^2 n + \sum q)$

---

关键公式总结

$$\boxed{\text{最终数组: } b_i = a_i \bmod x}$$ $$\boxed{\text{中位数条件: } \#\{i : a_i \bmod x \le m\} \ge \lfloor n/2 \rfloor + 1} $$$$\boxed{\#\{i : a_i \bmod x \le m\} = \sum_{k=0}^{\lfloor n/x \rfloor} \text{count}(k \cdot x, k \cdot x + m)} $$