sort排序

在生活和其他地方，排序是必不可少的。在OJ刷题时，你是否通常先按照题目难度排序，然后从简单题目刷起（一个可能打扰你的兴致的建议：长期刷简单题没用）。排序算法有很多，其实sort就够用了（除非考你基础概念）。

sort函数使用了多种排序方法，例如：快速排序、归并排序……能最大化优化时间复杂度。

使用方法：sort(begin, end, cmp);

begin -> 排序的开始位置

end -> 排序的结束位置

cmp -> 自定义排序函数（默认从小到大排序，如果有其他需求再写）

例：从a[0]~a[n-1]从小到大排序

$$
sort(a, a + n);
$$

如果需要从大到小排序时，要写cmp函数：

1
2
3
bool cmp(int a, int b) {
    return a > b;
}

再写sort函数：

1
sort(a, a + n, cmp);

例题P1177 【模板】排序

P1177 【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

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

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例 #1

输入 #1

1
2
5
4 2 4 5 1

输出 #1

1
1 2 4 4 5

说明/提示

对于 $20%$ 的数据，有 $1 \leq N \leq 10^3$；

对于 $100%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。

一个非常简单的模板题。只需要输入后sort一下最后输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1); // 从a[1]~a[n]排序
    for(int i = 1; i <= n; ++i)
        cout << a[i] << " ";
    return 0; 
}

递推与递归

有的目标是十分宏大的，比如想考上清华大学，如果现在还是一个小学生（我就是），那么想要达到这个目标太遥远太难了，但如果把这个宏大的目标分解成一个个小的子任务，就不会感觉困难了（短期目标的重要性）。如何进入清华呢？要高考考好。怎么考好呢？上好高中。怎么上好高中？首先要考上高中，还要努力学习……直到最后只剩下最基础的任务。

像这样将一个很大的任务分解成规模小一些的子任务，子任务分解成更小的子任务，直到遇到初始条件，最后整理归纳解决大任务的思想就是递推与递归的思想，不过两者有一些区别。

B2064 斐波那契数列

B2064 斐波那契数列

题目描述

斐波那契数列是指这样的数列：数列的第一个和第二个数都为 $1$，接下来每个数都等于前面 $2$ 个数之和。

给出一个正整数 $a$，要求斐波那契数列中第 $a$ 个数是多少。

输入格式

第 $1$ 行是测试数据的组数 $n$，后面跟着 $n$ 行输入。每组测试数据占 $1$ 行，包括一个正整数 $a$（$1 \le a \le 30$）。

输出格式

输出有 $n$ 行，每行输出对应一个输入。输出应是一个正整数，为斐波那契数列中第 $a$ 个数的大小。

输入输出样例 #1

输入 #1

1
2
3
4
5
4
5
2
19
1

输出 #1

1
2
3
4
5
1
4181
1

这道题目就是最基础的递推（递归）题目，我会用递推和递归两种解法说明。

递推

递推是动态规划的基础。什么是动态规划？一种算法，在CSP-J要考，S要考，NOIP要考，NOI要考……总之学好递推很重要，为动态规划打下基础。

现在理解递推就可以理解为是循环+递推公式。递推公式是什么？简单来说就是要在循环里写的语句，比如要求出a[i] = ?，那么你可以从以前已经记录过的数据（a[i - 1]……）去转移过来（在动态规划里，递推公式叫状态转移方程）。

在做递推或dp（动态规划的简称）时，有几个步骤。

  1. 建立一个dp数组，维度视情况决定。要明确这个数组的每一个位置（也就是状态）是干什么的！在这道题目中，我们建立一维dp数组，dp[i]表示斐波那契数列的第i位。

  2. 确定初始状态，也就是最基本的一位，这道题里初始状态就是数列的第一和第二位是1。

  3. 明确递归公式（状态转移方程），这个是如何从以前存储过的数据转移到现在的状态。在这道题目中，状态转移方程是dp[i] = dp[i - 1] + dp[i - 2]，意思是斐波那契数列的第 i 为是由数列的第 i - 1 位 + 第 i - 2 位。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        int dp[40];
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= a; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        cout << dp[a] << endl;
    }
    return 0;
}