AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

第一章 基础算法(一) 学习笔记

作者: 作者的头像   Immelon ,  2022-08-06 10:27:31 ,  所有人可见 ,  阅读 25


1


主要讲了三个基础算法的思想和模板,以及一些例题

基础算法思想和模板

快速排序

思想:对于所要排序的区间,设置两个指针为 i(初始值为 l-1 ) 和 j(初始值为 r+1 ),以及一个枢纽值(一般取中间位置的值),将 i 和 j 移动到可以进行交换的地方(i 位置的值大于枢纽值时可交换,j 位置的值小于枢纽值时可交换),进行交换,直至 i 与 j 相遇( 满足i>=j )。
然后对由i(或者 j )分割开的左右两个区间分别进行快速排序。

#include <iostream>
#include <algorithm>

const int N = 1000010;
int n;
int q[n];

using namespace std;

void quick_sort(int q[], int l, int r)
{
    if(l>=r) return;
    int i=l-1, j=r+1, x=q[l+r>>1];
    while(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, i);
    quick_sort(q, i+1, r);
}
int main(void)
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d", &q[i]);

    quick_sort(q, 0, n-1);

    for(int i=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个边界问题
1. 循环的大条件是while(i<j),而不是while(i<=j)
2. 判断左移和右移是<和>而不是<=和>=
以上两个地方从思路上来考虑没有问题,但是在实际数据中运行可能会导致无限循环,所以要记得这两个地方。

归并排序

思想:对于所要排序的区间,设置两个指针 i(初始值为区间左边界 l)和 j(初始值为区间中间位置 l+r>>1),两者后移时将所指向的较小值放入 tmp[] 数组,直至 i==mid 或者 j==r,然后把左半边或者右半边剩余的全部移进 tmp[] 数组,实现排序,最后把 tmp[] 数组中的元素拷贝到原数组的[l, r]区间。
注意,递归的位置在排序之前。

#include <iostream>

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

using namespace std;

void merge_sort(int q[], int l, int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    int i=l, j=mid+1, k=0;
    merge_sprt(q, l, mid);
    merge_sort(q, mid+1, r);
    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(void)
{
    scanf("%d", &n);

    for(int i=0; i<n; i++) scanf("%d", &q[i]);

    merge_sort(q, 0, n-1);

    for(int i=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个问题
1. 递归在排序之前
2. i=l, j=mid+1
3. tmp[] 数组从0开始存放和拷贝

二分查找

思想:对于一个区间,如果某种性质能够将区间分为前后两个部分(check()为True和False),那么可以用递归的方式找到满足与不满足的分界点,递归的方式是逐步地缩小查找的区间,并且每次只check此区间中间位置的值是否满足,注意这里“递归”的实现是循环。

bool check(int x) // 检查是否满足某种性质
{
    /* ... */
}

int bsearch_1(int l, int r)
{
    while(l<r)
    {
        int mid= l+r >> 1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

int bsearch_2(int l, int r)
{
    while(l<r)
    {
        int mid= l+r+1 >>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

bool check(double x)// 检查是否满足某种性质
{
    /* ... */
}

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;
    while(r-l>eps)
    {
        double mid = (l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    return l;
}

需要注意的问题
1. 如果所写的check()函数为 True 时,需要将 l 更新为 mid,那么 mid 应该用 l+r+1 >> 1(原因可能是正整数移位取整是向下取整,不+1 可能会导致 l=l,从而导致无无限循环)

0 评论

你确定删除吗?

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息