给定 $n$ 个不同的数 $a_1 \dots a_n$ 。求 $n$ 个数字当中第 $l$ 到第 $r$ 个数当中的中位数，我们可以用二分的经典思想来解决此问题。
所谓中位数就是 $n$ 个数中从小到大排序第 $\lfloor \frac{n}{2} \rfloor$ 个数。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int n, m, a[MAXN], maxn;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], maxn = max(maxn, a[i]);
while (m--) {
int lft, rgt;
cin >> lft >> rgt;
int l = 1, r = ___(1)___;
while (___(2)___) {
int mid = ___(3)___, s1 = 0, s2 = 0;
for (int i = lft; i <= rgt; i++) {
if (a[i] > mid) s1++;
if (a[i] < mid) s2++;
}
if (s1 < s2) ___(4)___ = mid;
else ___(5)___ = mid;
}
cout << l;
}
return 0;
}
1. C。
2. D。
3. D。
4. B。
5. A。
对于每个询问的区间，通过二分的方式来寻找中位数。每次二分一个 $mid$，查找序列中有多少个数字是小于它或大于它的，根据这个数字再继续进行二分过程直到退出二分。注意由于这里使用的二分中使用的区间是 $[l, r)$，所以变量 $r$ 是 $maxn+1$ 。