一、基础算法

基础算法内容目录

排序
二分
高精度
前缀和与差分
双指针算法
位运算
离散化
区间合并

1、排序

快速排序

  • 问题描述

    AcWing 785. 快速排序

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤1000001≤n≤100000

输入样例：

1
2
5
3 1 2 4 5

输出样例：

1
1 2 3 4 5
  • 题解
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
#include <stdio.h>

#define N 100010	//定义数据范围 
int q[N]; 

void quick_sort(int q[],int l,int r)//快速排序模板 
{
	if(l == r) return;//判断边界，指针已穿过，此时区间有0或1个数直接退出排序 
	
	int x = q[(l+r)/2],i = l - 1,j = r + 1;//取中间点为分界点，初始化指针指向边界两侧，保证循环时指向正真边界 
	while (i < j)//调整左右两个区间 
	{
		do i++ ;while(q[i] < x);
		do j-- ;while(q[j] > x);
		if(i < j)
        {
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }//此时i,j已停下来，交换它们指向的数 
	}
	quick_sort(q,l,j);//再递归左右两段，直到有序 
	quick_sort(q,j+1,r);	
}

int main(){
	int n;
	scanf("%d",&n);//读入排序个数 
	for(int i = 0;i < n;i++) scanf("%d",&q[i]);//存入数组q[i] 
	quick_sort(q,0,n-1);//调用快排，传入数据及左右边界 
	for(int i = 0;i < n;i++) printf("%d ",q[i]);
	return 0;
}

归并排序

  • 问题描述

    AcWing 787. 归并排序

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

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

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

    输入格式

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

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

    输出格式

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

    数据范围

    1≤n≤1000001≤n≤100000

    输入样例

    1
    2
    5
    3 1 2 4 5

    输出样例：

    1
    1 2 3 4 5
  • 题解
    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 <stdio.h>

    #define N 100010
    int q[N],temp[N];

    void merge_sort(int q[],int l,int r)//归并排序模板 
    {
    	if(l == r) return;//当前区间有0或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;//初始化左右起点i,j 
    	while(i <= mid && j <= r)
    	{
    		if(q[i] <= q[j]) temp[k++] = q[i++];//每次把小的数存入辅助数组temp 
    		else temp[k++] = q[j++];
    	}
    	while(i <= mid) temp[k++] = q[i++];//左边没循环完时，直接复制给temp 
    	while(j <= r) temp[k++] = q[j++];
    	
    	for(i = l,j = 0;i <= r;i++,j++) q[i] = temp[j];//这里取最后一次排好序的temp值，把辅助数组存回原数组 
    }

    int main()
    {
    	int n; 
    	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;
    }

2、二分

整数二分算法

  • 问题描述

    AcWing 789. 数的范围

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

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

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

    输入格式

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

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

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

    输出格式

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

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

    数据范围

    1≤n≤1000001≤n≤100000
    1≤q≤100001≤q≤10000
    1≤k≤100001≤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
  • 题解
    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
    #include <stdio.h>

    #define N 100010
    int n,q;
    int a[N];

    int main()
    {
        scanf("%d%d",&n,&q);
        for(int i = 0; i < n; i++)  scanf("%d",&a[i]);
        
        while(q--)
        {
            int x;
            scanf("%d",&x);
            int l = 0, r = n - 1;
            while(l < r)
            {
                int mid = (l + r)/2;
                if(a[mid] >= x) r = mid;
                else l = mid + 1;
            }
            if(a[l] != x)   printf("-1 -1\n");
            else
            {
                printf("%d ",l);
                int l = 0,r = n - 1;
                while(l < r)
                {
                    int mid = (l + r + 1)/2;
                    if(a[mid] <= x) l = mid;
                    else r = mid -1;
                }
                printf("%d \n",l);
            }
        }
        return 0;
    }

浮点数二分算法

  • 问题描述

    AcWing 790. 数的三次方根

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

    输入格式

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

    输出格式

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

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

    数据范围

    −10000≤n≤10000−10000≤n≤10000

    输入样例：

    1
    1000.00

    输出样例：

    1
    10.000000
  • 题解
    1
    2