普及二分https://www.luogu.com.cn/problem/B3627



# 立方根

## 题目描述

给定正整数 $n$，求 $\sqrt[3]{n}$。答案向下取整。

## 输入格式

仅一行，一个正整数 $n$。

## 输出格式

仅一行，一个正整数，表示 $\sqrt[3]n$。向下取整输出。

## 样例 #1

### 样例输入 #1

```
27
```

### 样例输出 #1

```
3
```

## 样例 #2

### 样例输入 #2

```
100000
```

### 样例输出 #2

```
46
```

## 样例 #3

### 样例输入 #3

```
1000000000000000
```

### 样例输出 #3

```
100000
```

## 提示

对于 $100\%$ 的数据，有 $n\leq 10^{15}$。



```c

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);

    long long left = 0, right = n;
    long long result = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        long long mid_cubed = mid * mid * mid;

        if (mid_cubed <= n) {
            result = mid; // 记录当前的 mid 值
            left = mid + 1; // 尝试更大的值
        } else {
            right = mid - 1; // 尝试更小的值
        }
    }

    printf("%lld\n", result);

    return 0;
}

```



库函数
```c
#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    scanf("%lld", &n);

    long long result = cbrt(n);
    printf("%lld\n", result);

    return 0;
}
```

9.22普及算法

2014.12阅读精读

## 1.なんといっても

「なんといっても」は、「どんなことを言っても」「どう考えても」という意味で、主に強調や断定を表す表現です。以下に5つの例文を示します。

1. **なんといっても、彼は優秀な選手だ。**  
   (どんなことを言っても、彼は優秀な選手だ。)  
   （无论如何，他都是一个优秀的选手。）

2. **なんといっても、健康が一番だ。**  
   (どんなことを言っても、健康が一番だ。)  
   （无论如何，健康都是最重要的。）

3. **なんといっても、彼女の料理は美味しい。**  
   (どんなことを言っても、彼女の料理は美味しい。)  
   （无论如何，她的料理都非常美味。）

4. **なんといっても、この映画は面白かった。**  
   (どんなことを言っても、この映画は面白かった。)  
   （无论如何，这部电影都非常有趣。）

5. **なんといっても、彼の努力は認めるべきだ。**  
   (どんなことを言っても、彼の努力は認めるべきだ。)  
   （无论如何，他的努力都值得认可。）

この表現は、ある事柄に対して強い確信や断定的な意見を表現する際によく使われます。


## 2.何とも…ない
「何とも…ない」は、「特に感じない」「特に言うことはない」という意味で、主に何かに対する感想や評価がないことを表す表現です。以下に5つの例文を示します。

1. **この映画は何とも言えない。**  
   (この映画は特に感じない。)  
   （这部电影没什么特别的感受。）

2. **彼の言葉は何とも思わなかった。**  
   (彼の言葉は特に感じなかった。)  
   （他的话我没什么特别的感觉。）

3. **この料理は何とも美味しくない。**  
   (この料理は特に美味しくない。)  
   （这道菜没什么特别的美味。）

4. **彼の態度は何とも気にならなかった。**  
   (彼の態度は特に気にならなかった。)  
   （他的态度我没什么特别在意。）

5. **この本は何とも面白くない。**  
   (この本は特に面白くない。)  
   （这本书没什么特别的趣味。）

この表現は、何かに対して特に感想や評価がないことを表現する際によく使われます。

## 3.何とかして
「何とかして」は、「どうにかして」「必ずしも簡単ではないが、努力して」という意味で、主に困難な状況を克服しようとする意志や決意を表す表現です。以下に5つの例文を示します。

1. **何とかして、この仕事を完成させたい。**  
   (どうにかして、この仕事を完成させたい。)  
   （无论如何，我都想完成这项工作。）

2. **何とかして、彼女との関係を修復したい。**  
   (どうにかして、彼女との関係を修復したい。)  
   （无论如何，我都想修复与她的关系。）

3. **何とかして、この試験に合格したい。**  
   (どうにかして、この試験に合格したい。)  
   （无论如何，我都想通过这次考试。）

4. **何とかして、この問題を解決したい。**  
   (どうにかして、この問題を解決したい。)  
   （无论如何，我都想解决这个问题。）

5. **何とかして、彼の気持ちを理解したい。**  
   (どうにかして、彼の気持ちを理解したい。)  
   （无论如何，我都想理解他的心情。）

この表現は、困難な状況に直面しているが、それを克服しようとする強い意志や決意を表現する際によく使われます。


## 4.いずれにしても
「いずれにしても」は、「どちらにせよ」「どういう結果になっても」という意味で、主にどんな状況でも同じ結論や行動を取ることを表す表現です。以下に5つの例文を示します。

1. **いずれにしても、明日は早く起きなければならない。**  
   (どちらにせよ、明日は早く起きなければならない。)  
   （无论如何，明天都必须早起。）

2. **いずれにしても、彼は来週の会議に出席するだろう。**  
   (どちらにせよ、彼は来週の会議に出席するだろう。)  
   （无论如何，他都会出席下周的会议吧。）

3. **いずれにしても、この計画は変更される可能性がある。**  
   (どちらにせよ、この計画は変更される可能性がある。)  
   （无论如何，这个计划都有可能被修改。）

4. **いずれにしても、私は彼の意見を尊重するつもりだ。**  
   (どちらにせよ、私は彼の意見を尊重するつもりだ。)  
   （无论如何，我都打算尊重他的意见。）

5. **いずれにしても、この問題は解決しなければならない。**  
   (どちらにせよ、この問題は解決しなければならない。)  
   （无论如何，这个问题都必须解决。）

この表現は、どんな状況でも同じ結論や行動を取ることを表現する際によく使われます。

## 5.ものと思われる

「ものと思われる」は、「そう考えられる」「そう思われる」という意味で、主に推測や推論を表す表現です。以下に5つの例文を示します。

1. **彼が遅刻した理由は、交通渋滞だったものと思われる。**  
   (彼が遅刻した理由は、交通渋滞だったと考えられる。)  
   （他迟到的原因，应该是交通堵塞。）

2. **この事件は内部告発によるものと思われる。**  
   (この事件は内部告発によると考えられる。)  
   （这起事件，应该是由内部告发引起的。）

3. **彼女は今回のプロジェクトに成功したものと思われる。**  
   (彼女は今回のプロジェクトに成功したと考えられる。)  
   （她这次的项目，应该是成功了。）

4. **この製品は人気があるものと思われる。**  
   (この製品は人気があると考えられる。)  
   （这款产品，应该是很受欢迎的。）

5. **彼は無実だったものと思われる。**  
   (彼は無実だったと考えられる。)  
   （他应该是无辜的。）

この表現は、何かについての推測や推論を表現する際によく使われます。


（新系列）每日文法

2014.7阅读精读

今天做https://www.luogu.com.cn/problem/P1168


# 中位数
## 题目描述
给定一个长度为 $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$。



用到的对顶堆算法


对顶堆算法（Median Maintenance Algorithm）是一种用于动态维护中位数的算法。它的核心思想是使用两个堆来分别存储数据集的较小一半和较大一半的元素，从而能够快速找到中位数。
### 核心思想：
1. **两个堆**：
   - **大顶堆（max heap）**：存储较小的一半元素。
   - **小顶堆（min heap）**：存储较大的一半元素。
2. **平衡条件**：
   - 大顶堆的堆顶元素是较小一半的最大值。
   - 小顶堆的堆顶元素是较大一半的最小值。
   - 两个堆的大小差不能超过1。
3. **中位数**：
   - 如果两个堆的大小相等，中位数是两个堆顶元素的平均值。
   - 如果两个堆的大小不相等，中位数是较大堆的堆顶元素。
### 具体步骤：
1. **初始化两个堆**：
   - `max_heap`：大顶堆，存储较小的一半元素。
   - `min_heap`：小顶堆，存储较大的一半元素。
2. **遍历序列**：
   - 对于每个元素，先将其插入到大顶堆中。
   - 检查大顶堆和小顶堆的大小关系：
     - 如果大顶堆的元素数量比小顶堆的元素数量多出2个或更多，则将大顶堆的堆顶元素移到小顶堆中。
     - 如果大顶堆的堆顶元素大于小顶堆的堆顶元素，则交换这两个堆的堆顶元素。
3. **输出中位数**：
   - 每次处理完奇数个元素后，大顶堆的堆顶元素就是当前序列的中位数。
### 具体例子：
假设输入序列为 `[3, 1, 5, 9, 8, 7, 6]`，我们逐步分析：
1. **插入第一个元素 `3`**：
   - `max_heap`：`[3]`
   - `min_heap`：空
   - 中位数：`3`
   - 输出：`3`
2. **插入第二个元素 `1`**：
   - `max_heap`：`[3, 1]`
   - `min_heap`：空
   - 调整：`max_heap` 的元素数量比 `min_heap` 多出2个，将 `3` 移到 `min_heap`
   - `max_heap`：`[1]`
   - `min_heap`：`[3]`
   - 中位数：`3`
   - 输出：`3`
3. **插入第三个元素 `5`**：
   - `max_heap`：`[5, 1]`
   - `min_heap`：`[3]`
   - 调整：`max_heap` 的堆顶元素 `5` 大于 `min_heap` 的堆顶元素 `3`，交换
   - `max_heap`：`[3, 1]`
   - `min_heap`：`[5]`
   - 中位数：`3`
   - 输出：`3`
4. **插入第四个元素 `9`**：
   - `max_heap`：`[9, 3, 1]`
   - `min_heap`：`[5]`
   - 调整：`max_heap` 的元素数量比 `min_heap` 多出2个，将 `9` 移到 `min_heap`
   - `max_heap`：`[3, 1]`
   - `min_heap`：`[5, 9]`
   - 中位数：`5`
   - 输出：`5`
5. **插入第五个元素 `8`**：
   - `max_heap`：`[8, 3, 1]`
   - `min_heap`：`[5, 9]`
   - 调整：`max_heap` 的堆顶元素 `8` 大于 `min_heap` 的堆顶元素 `5`，交换
   - `max_heap`：`[5, 3, 1]`
   - `min_heap`：`[8, 9]`
   - 中位数：`5`
   - 输出：`5`
6. **插入第六个元素 `7`**：
   - `max_heap`：`[7, 5, 3, 1]`
   - `min_heap`：`[8, 9]`
   - 调整：`max_heap` 的元素数量比 `min_heap` 多出2个，将 `7` 移到 `min_heap`
   - `max_heap`：`[5, 3, 1]`
   - `min_heap`：`[7, 8, 9]`
   - 中位数：`6`
   - 输出：`6`
7. **插入第七个元素 `6`**：
   - `max_heap`：`[6, 5, 3, 1]`
   - `min_heap`：`[7, 8, 9]`
   - 调整：`max_heap` 的堆顶元素 `6` 大于 `min_heap` 的堆顶元素 `7`，交换
   - `max_heap`：`[5, 3, 1]`
   - `min_heap`：`[6, 7, 8, 9]`
   - 中位数：`6`
   - 输出：`6`
### 复杂度分析：
- **时间复杂度**：每次插入和调整堆的时间复杂度为 $O(\log k)$，其中 $k$ 是当前堆的大小。总的时间复杂度为 $O(N \log N)$。
- **空间复杂度**：两个堆的空间复杂度为 $O(N)$。
### 代码实现：
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void find_medians(int N, vector<int>& A) {
    priority_queue<int> max_heap;  // 大顶堆，存储较小的一半元素
    priority_queue<int, vector<int>, greater<int>> min_heap;  // 小顶堆，存储较大的一半元素
    
    for (int i = 0; i < N; ++i) {
        // 将当前元素插入到大顶堆中
        max_heap.push(A[i]);
        
        // 如果大顶堆的元素数量比小顶堆的元素数量多出2个或更多
        if (max_heap.size() > min_heap.size() + 1) {
            // 将大顶堆的堆顶元素移到小顶堆中
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
        
        // 如果大顶堆的堆顶元素大于小顶堆的堆顶元素
        if (!min_heap.empty() && max_heap.top() > min_heap.top()) {
            // 交换这两个堆的堆顶元素
            int max_top = max_heap.top();
            int min_top = min_heap.top();
            max_heap.pop();
            min_heap.pop();
            max_heap.push(min_top);
            min_heap.push(max_top);
        }
        
        // 如果当前处理的是奇数个元素
        if ((i + 1) % 2 == 1) {
            // 输出大顶堆的堆顶元素，即当前序列的中位数
            cout << max_heap.top() << endl;
        }
    }
}
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    find_medians(N, A);
    
    return 0;
}
```
巧妙的利用了大小堆的性质

立方

短篇1

1.なんといっても

短篇1

中位数