# AcWing 785. 快速排序

# 题目描述

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

# 输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

# 输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

# 数据范围

1≤n≤100000

# 输入样例：

1
2
5
3 1 2 4 5

# 输出样例：

1
1 2 3 4 5

# 解题思路

# 题意理解

这道题目显然是要我们将一个无序数列排序，成为具有升序性质的升序序列.

# 算法处理

一道排序题目，数据范围是关键，我们发现这道题目只能让我们使用 O (nlogn) 的算法，显然我们可以选择快速排序，归并排序等算法，这里我们就使用快速排序.

# 代码实现

# C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[],int l,int r) {
    
    if(l >= r) return; // 如果没有数据或者只有一个数字的话，则不用排序
    
    int x = q[(l + r) / 2],i = l - 1, j = r + 1; // 确定分界点和指针
    // 注意：分界点有四种取法，这里取的是中间的数据
    
    while(i < j) { // i和j未相遇时，一直循环
        do i++; while(q[i] < x); // 寻找
        do j--; while(q[j] > x); // 寻找
        if(i < j) swap(q[i],q[j]); // 未相遇则交换，相遇了就不交换
        
    }
    
    // 继续对整理出的两段数据进行排序
    quick_sort(q, l, j); 
    quick_sort(q, j + 1, r);
}

int main() {
    
    scanf("%d",&n);
    for(int i = 0; i < n ; i++) scanf("%d",&q[i]);
    
    quick_sort(q, 0 ,n-1);
    
    for(int i = 0; i < n ; i++) printf("%d ",q[i]);
    
    return 0;
}

# Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

package 基础算法;

import java.util.Scanner;

public class Quick_Sort { // 快速排序

    public static int N = (int) (1e6 +10);
    public static int n; // 要排序的整数的个数
    public static int [] p = new int[N];

    public static void quick_sort(int[] p,int l,int r) {
        if(l >= r) return; // 如果没有数据或者只有一个数字的话，则不用排序

        int x = p[(l + r)/2],i = l - 1,j = r + 1;// 确定分界点和指针
        // 注意：分界点有四种取法，这里取的是中间的数据

        while(i < j) { // i和j未相遇时，一直循环
            do i++; while(p[i] < x); // 寻找
            do j--; while(p[j] > x); // 寻找
            if(i < j) { // 指针未相遇则交换，相遇了就不交换
                int t = p[i];
                p[i] = p[j];
                p[j] = t;
            }
        }

        quick_sort(p,l,j); // 递归处理左半边
        quick_sort(p,j+1,r); // 递归处理右半边

    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        n = in.nextInt();

        for (int i = 0;i < n;i++) {
            p[i] = in.nextInt();
        }

        quick_sort(p,0,n-1); // 快排

        for (int i = 0;i < n;i++) {
            System.out.println(p[i]);
        }

    }
}

# AcWing 787. 归并排序

# 题目描述

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

# 输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

# 输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

# 数据范围

1≤n≤100000

# 输入样例：

1
2
5
3 1 2 4 5

# 输出样例：

1
1 2 3 4 5

# 解题思路

# 题意理解

这道题目还是让我们排序，只不过这里强制要求我们使用归并排序，所以既然如此的话，让我们好好地康康这道题目.

# 算法处理

归并排序，它有两大核心操作.

一个是将数组一分为二，一个无序的数组成为两个数组.

另外一个操作就是，合二为一，将两个有序数组合并成为一个有序数组.

# 代码实现

# C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;

const int N = 1e6 + 10;

int n; // 要排序的整数的个数
int q[N],tmp[N]; // 排序的数组和功能数组

void merge_sort(int q[],int l,int r) { // 归并排序

    if(l >= r) return;
    
    int mid = (l + r) >> 1; // 选取中间点，相当于 int mid = (l+r) / 2;
    
    merge_sort(q,l,mid); // 对左半部分进行递归
    merge_sort(q,mid+1,r); // 对右半部分进行递归
    
    int k = 0,i = l,j = mid+1; // 设置递归左右两边区域时使用的三个指针
    while(i <= mid && j <= r) // 左右两边都没遍历完的时候
        if(q[i] <= q[j]) tmp[k++] = q[i++]; // 后指针指的数字更小的话，将后指针所指数字放入功能数组并指向下一位
        else tmp[k++] = q[j++]; // 前指针指的数字更小的话，将前指针所指数字放入功能数组并指向下一位
    
    // 将未遍历完的部分放入功能数组
    while(i <= mid) tmp[k++] = q[i++]; // 将前半部分未遍历完的部分放入功能数组
    while(j <= r) tmp[k++] = q[j++]; // 将后半部分未遍历完的部分放入功能数组
    
    for(i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j]; // 将功能数组中排好序的数字复制到原始数组中
    
}

int main() {
    
    scanf("%d",&n);
    for(int i = 0;i < n;i++) scanf("%d",&q[i]);
    
    merge_sort(q,0,n-1);
    
    for(int i = 0;i < n;i++) printf("%d ",q[i]);
    
    return 0;
}

# Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package 基础算法;

import java.util.Scanner;

public class Merge_Sort {

    public static int N = (int) (1e6 +10);
    public static int n; // 要排序的整数的个数
    public static int [] p = new int[N];
    public static int [] tmp = new int[N];

    public static void merge_sort(int[] p,int l,int r) {
        if(l >= r) return;

        int mid = (l + r) >> 1; // 选取中间点，相当于 int mid = (l+r) / 2;

        merge_sort(p,l,mid); // 对左半部分进行递归
        merge_sort(p,mid+1,r); // 对右半部分进行递归

        int k = 0,i = l,j = mid+1; // 设置递归左右两边区域时使用的三个指针  // 这句易错
        while(i <= mid && j <= r) // 左右两边都没遍历完的时候
            if(p[i] <= p[j]) tmp[k++] = p[i++]; // 后指针指的数字更小的话，将后指针所指数字放入功能数组并指向下一位
            else tmp[k++] = p[j++]; // 前指针指的数字更小的话，将前指针所指数字放入功能数组并指向下一位

        // 将未遍历完的部分放入功能数组
        while(i <= mid) tmp[k++] = p[i++]; // 将前半部分未遍历完的部分放入功能数组
        while(j <= r) tmp[k++] = p[j++]; // 将后半部分未遍历完的部分放入功能数组

        for(i = l,j = 0;i <= r;i++,j++) p[i] = tmp[j]; // 将功能数组中排好序的数字复制到原始数组中

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 0;i < n;i++) {
            p[i] = in.nextInt();
        }

        merge_sort(p,0,n-1); // 快排

        for (int i = 0;i < n;i++) {
            System.out.println(p[i]);
        }
    }

}

# AcWing 789. 数的范围（二分）

# 题目描述

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1 。

# 输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

# 输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1 。

# 数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

# 输入样例：

1
2
3
4
5
6 3
1 2 2 3 3 4
3
4
5

# 输出样例：

1
2
3
3 4
5 5
-1 -1

# 解题思路

# 整数二分

二分的本质是二段性不是单调性。

当想找不满足性质的边界值（红色区域的右边界值）

找中间值 mid = (l+r+1)/2
if (check (mid)) 等于 true 或者是 false
check (m) 是检查 m 是在不满足性质的区间（检查是不是在红色区间）
更新 l 或者 r

当想找满足性质的边界值（绿色区域的左边界值）

  1. 找中间值 mid = (l+r)/2
  2. if (check (mid)) 等于 true 或者是 false
    check (m) 是检查 m 是在满足性质的区间（检查是不是在绿色区间）
  3. 更新 l 或者 r

归结上面的两种二分方法，步骤为：

  1. 先写一个 check 函数
  2. 判定在 check 的情况下（true 和 false 的情况下），如何更新区间。
  3. 在 check (m)==true 的分支下是:
    1. l=mid 的情况，中间点的更新方式是 m=(l+r+1)/2
    2. r=mid 的情况，中间点的更新方式是 m=(l+r)/2

这种方法保证了：

  1. 最后的 l==r
  2. 搜索到达的答案是闭区间的，即 a [l] 是满足 check () 条件的。

# 代码实现

# Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Scanner;

public class Main {
    
    public static int N = (int)1e5+10;
    public static int n,m;
    public static int[] q = new int[N];
    
    public static void main(String[] srgs) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); // 读入数组长度
        m = in.nextInt(); // 读入询问个数
        for(int i = 0;i <n;i++) q[i] = in.nextInt(); // 读入数组数据

        while(m-- > 0) { // 询问个数大于0（还未询问完）
            int x;
            x = in.nextInt(); // 读入要询问的数字

            int l = 0, r = n - 1; // 选取左右指针(数组的左右两边)
            while (l < r) { // 当指针未相遇时(未找到想找到的边界时)
                int mid = l + r >> 1; // mid = l // 定义中间量 用于检查数据和更新指针
                if (q[mid] >= x) r = mid; // 更新右指针
                else l = mid + 1; // 更新左指针
            }
            if (q[l] != x) System.out.println("-1 -1"); // 未找到想要的边界(未找到想要的数字(找到的位置上的数字不是我们想要的))
            else {
                System.out.print(l + " "); // 输出我们想要的左边界(查询的数字第一次出现的位置)
                l = 0;r = n - 1; // 重新选取选取左右指针(数组的左右两边)
                while (l < r) { // // 当指针未相遇时(未找到想找到的边界时)
                    int mid = l + r + 1 >> 1; // mid = r // 重新定义中间量 用于检查数据和更新指针
                    if (q[mid] <= x) l = mid; // 更新左指针
                    else r = mid - 1; // 更新右指针
                }
                System.out.println(l); // 输出我们想要的右边界(查询的数字最后一次出现的位置)

            }
        }
        
        
    }
    
}

# C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
using namespace std;

int n,m;
const int N = 1e6+10;
int q[N];

int main() {
    
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++) 
        scanf("%d",&q[i]);
    
    while(m--) { // 询问个数大于0（还未查询完）
        int x = 0;
        scanf("%d",&x); // 读入要查询的数字
        
        int l = 0,r = n-1; // 选取左右指针（数组的左右两边）
        
        // 确定左边界（第一次出现的位置）
        while(l < r) { // 当指针未相遇时(未找到想找到的边界时)）
            int mid = (l + r) >> 1; // mid = l // 定义中间量 用于检查数据和更新指针
            if(q[mid] >= x) r = mid; // 更新右指针
            else l = mid+1; // 更新左指针
        }
        if(q[l] != x) cout << "-1 -1" << endl; // 未找到想要的边界(未找到想要的数字(找到的位置上的数字不是我们想要的))
        else {
            cout << l << " " ; // 输出我们想要的左边界(查询的数字第一次出现的位置)
            l = 0,r = n-1; // 重新选取选取左右指针(数组的左右两边)
            
            // 确定左边界（第一次出现的位置）
            while(l < r) { // 当指针未相遇时(未找到想找到的边界时)
                int mid = (l + r + 1) >> 1; // mid = r // 重新定义中间量 用于检查数据和更新指针
                if(q[mid] <= x) l = mid; // 更新左指针
                else r = mid-1; // 更新右指针
            }
            cout << l << endl; // 输出我们想要的右边界(查询的数字最后一次出现的位置)
            
        }
        
    }
    
    return 0;
}

# AcWing 790. 数的三次方根（二分）

# 题目描述

给定一个浮点数 n，求它的三次方根。

# 输入格式

共一行，包含一个浮点数 n。

# 输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

# 数据范围

−10000≤n≤10000

# 输入样例：

1
1000.00

# 输出样例：

1
10.000000

# 解题思路

学会整数二分后，相信这个大家有手就行。

# 代码实现

# C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

double x;

int main() {
    cin >> x; // 读入数据
    double l = -10000,r = 10000; // 设定范围
    
    while(r - l > 1e-8) { // 是否找到
        double mid = (l + r) / 2; // 中间值
        if(mid*mid*mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n",l); // %lf默认保留六位小数
    
    return 0;
}

# Java

JAVA 字符串格式化 ——String.format () 的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;

public class Main {

    public static void main(String[] srgs) {
        Scanner in = new Scanner(System.in);
        double x;
        x = in.nextDouble(); // 读入数据
        double l = -10000,r = 10000; // 设定范围
        while(r - l > 1e-8) { // 是否找到
            double mid = (l + r) / 2; // 中间值
            if(mid*mid*mid >= x) r = mid;
            else l = mid;
        }
        System.out.println(String.format("%.6f", l)); // 保留六位小数
        // System.out.printf("%.6f",l); // 作用相同
    }
    
}

# AcWing 791. 高精度加法

# 题目描述

给定两个正整数（不含前导 00），计算它们的和。

# 输入格式

共两行，每行包含一个整数。

# 输出格式

共一行，包含所求的和。

# 数据范围

1≤整数长度≤1000001≤整数长度≤100000

# 输入样例：

1
2
12
23

# 输出样例：

1
35

# 解题思路

  1. 因为是长整数的加法运算，普通的数据类型无法存放，所以选择了 vector（也因为有 .size 这个函数才采用它）。

  2. 过长的数据使我选择了字符串来读入，用循环放入 vector 即可（将数字低位在前高位在后的放入）。

  3. 在循环中通过算子 t 来进行每一位的运算，并将下一次运算的进位算出： t /= 10; （参与下一位数的运算），剩余部分写入结果中： C.push_back(t%10); 。

  4. 循环结束（各位的运算完成）后，如果最高位时 0，则需要进一位： C.push_back(1);

# 代码实现

# C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
using namespace std;

vector<int> add(vector<int> &A,vector<int> &B) { // 使用引用传参，就不用再复制一遍了
    
    vector<int> C; // 储存结果
    
    int t = 0; // 运算的算子以及进位
    for(int i = 0;i < A.size() || i < B.size();i++) { // 加法运算，A或B未读完时，加法继续
        if(i < A.size()) t += A[i]; // 从个位数开始加，一次循环加一位
        if(i < B.size()) t += B[i]; // 从个位数开始加，一次循环加一位
        C.push_back(t%10); // 排除t中需要进位的部分并将剩下的放在C里面
        t /= 10; // 下一次运算时的进位
    }
    if(t) C.push_back(1); // 运算后最高位是0，则进1
    return C;
}

int main() {
    string a,b;
    vector<int> A,B;
    
    cin >> a >> b; // 使用字符串读入数据
    // 在下面一步时，注意字符串的末尾有'0'，所以有 size() - 1 
    // 而 a[i] - '0' 是为了拿到数据(eg: '2' - '0' = 0)
    for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0'); // 将数据放入vector中
    for(int i = b.size() - 1;i >= 0;i--) B.push_back(b[i] - '0'); // 将数据放入vector中
    
    vector<int> C = add(A,B); // 进行加法运算并将结果放入C中
    
    // 在下面这一步时，要注意size() - 1,不然的话结果前面会多一个0
    for(int i = C.size() - 1;i >= 0;i--) printf("%d",C[i]); // 输出结果
    
    return 0;
}

# AcWing 792. 高精度减法

# 题目描述

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。

# 输入格式

共两行，每行包含一个整数。

# 输出格式

共一行，包含所求的差。

# 数据范围

1≤整数长度≤105

# 输入样例：

1
2
32
11

# 输出样例：

1
21

# 解题思路

判断需要相减的两个数的大小，然后进行逐位相减。

# 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>

using namespace std;

// A - B 是否大于0
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size(); // 先看长度，长度长的大

    for (int i = A.size() - 1; i >= 0; i -- ) // 从个位开始比较，相同跳过这位数，不相同返回结果
        if (A[i] != B[i])
            return A[i] > B[i];

    return true; // 都相同，返回true(此时A - B = 0)
}

// 减法运算
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    // 从个位开始逐位相减
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t; // 减去上一次的借位
        if (i < B.size()) t -= B[i]; // 由于A>B,i有可能超出B的位数，需要验证
        C.push_back((t + 10) % 10); // 添加结果(包含t>0与t<0的情况) --> t>0: t%10,  t<0: (t + 10) % 10
        
        // 计算借位
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 消除结果前的0(eg: 111-110=001 , 需要去除两个数字 0 使结果变成 1 )
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b; // 读入数据为字符串
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); // 转换成数字
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); // 转换成数字

    vector<int> C; // 定义结果

    // A > B 时,sub(A, B),否则 sub(B, A),并输出一个'-'号
    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    // 输出结果
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;

    return 0;
}

# 写在后面

暂时先写这么多，学了其他的继续写（~~ 菜鸡嘤嘤