c++题目_P1168 中位数

news/2024/9/23 8:23:51/

# 中位数

## 题目描述

给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。

## 输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $A_{1\dots N}$。

## 输出格式

共 $\lfloor \frac{N + 1}2\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i - 1}$ 的中位数。

## 样例 #1

### 样例输入 #1

```
7
1 3 5 7 9 11 6
```

### 样例输出 #1

```
1
3
5
6
```

## 样例 #2

### 样例输入 #2

```
7
3 1 5 9 8 7 6
```

### 样例输出 #2

```
3
3
5
6
```

## 提示

对于 $20\%$ 的数据，$N \le 100$；

对于 $40\%$ 的数据，$N \le 3000$；

对于 $100\%$ 的数据，$1 \le N ≤ 100000$，$0 \le A_i \le 10^9$。

看到这一题我第一反应就是——

二分

于是我开始敲代码

0分代码

#include <bits/stdc++.h>  // 包含常用的标准库
using namespace std;  // 使用标准命名空间int main() {int n, a[99999], mx, mn;  // 声明变量 n, a, mx, mncin >> n;  // 从标准输入读取 nfor (int i = 1; i <= n; i++) {cin >> a[i];  // 从标准输入读取数组 a 的元素}for (int i = 1; i <= n; i += 2) {  // 遍历数组 a 的元素sort(a, a + i + 1);  // 对数组 a 进行排序，排序范围是 a[0] 到 a[i]mn = a[1];  // 最小值是排序后的第一个元素mx = a[i];  // 最大值是排序后的第 i 个元素int l = 1, r = i, mid, z = (mn + mx) / 2, ll;  // 声明变量 l, r, mid, z, llwhile (l <= r) {  // 当 l 小于等于 r 时循环mid = (l + r) >> 1;  // 取中间值if (a[mid] > z) {r = mid - 1;  // 如果中间值大于 z，将 r 更新为 mid - 1} else {l = mid + 1;  // 如果中间值小于等于 z，将 l 更新为 mid + 1}}ll = l;  // ll 为小于等于 z 的最大值的下标l = 1;  // 重置 lr = i;  // 重置 rwhile (l <= r) {  // 当 l 小于等于 r 时循环mid = (l + r) >> 1;  // 取中间值if (a[mid] < z) {l = mid + 1;  // 如果中间值小于 z，将 l 更新为 mid + 1} else {r = mid - 1;  // 如果中间值大于等于 z，将 r 更新为 mid - 1}}if (z - a[ll - 1] <= a[ll] - z) {cout << a[ll - 1] << endl;  // 如果 z 与小于等于 z 的最大值的差小于等于大于 z 的最小值与 z 的差，输出小于等于 z 的最大值} else {cout << a[ll] << endl;  // 否则，输出大于 z 的最小值}}return 0;  // 返回 0，表示成功
}

普普通通的二分，不会还有人不会吧！

于是我测了一下第一样例

过了

提交

错了

。。。

于是我旷然大悟

修改了我代码

40分代码

#include <bits/stdc++.h>  // 包含常用的标准库
using namespace std;  // 使用标准命名空间int main() {int n, a[99999], mx, mn;  // 声明变量 n, a, mx, mncin >> n;  // 从标准输入读取 nfor (int i = 1; i <= n; i++) {cin >> a[i];  // 从标准输入读取数组 a 的元素}for (int i = 1; i <= n; i += 2) {  // 遍历数组 a 的元素sort(a, a + i + 1);  // 对数组 a 进行排序，排序范围是 a[0] 到 a[i]cout << a[(1 + i) / 2] << endl;  // 输出排序后的数组中位数}return 0;  // 返回 0，表示成功
}