算法基础

CLJ大神保佑oier · 2018-12-31 18:18:18 · 个人记录

算法基础

二分

二分查找

• 二分查找，又名二分搜索，是一种在有序表中快速查找的算法

• 通常，我们维护一个答案可能存在的区间，将找到的值与区间中央的元素比较，不断缩小这个区间，直到区间里只有一个数

• 算法复杂度为O（\log_2n）

//从a数组中找到第一个大于等于x的值，并返回它的下标
//能取的地方越取，取不到的地方越不取确定开闭区间的左右
int chop(int n,int x){
    int l=0,r=n; //左开右闭区间
    while(l+1<r){
        int mid=(l+r)/2;
        if(a[mid]>=x) r=m;
        else l=m;
    }
    return r;
}

• 应用

  • 从有序数组里找给定的值

  • 从有序数组里找大于等于给定的值的最小的值

  • 寻找单调函数的零点

  • 求一些方程的近似解

  • 二分答案

二分答案

• 最优化问题：在满足某些条件的情况下，最大化（最小化）某个值

• 可行性问题：在满足某些条件的情况下，构造出一个合法方案

• 在做一些最优化问题时，我们会遇到这样的情况：直接做比较困难，但是假如我们把问题转化一下，变成可行性问题，会变得简单。并且答案是单调的，那么就可以使用二分答案的技巧

• 套用上面二分查找的写法，然后把判断条件变成判断目标答案是否可行

• 时间复杂度为O(log n)\times每次判断答案的时间

• 二分答案算法的套路：最大化xxx的最小值，最小化xxx的最大值

• 例题 P1873 砍树 P2678 跳石头

双指针

寻找数对

• 在单调数组中找两个数的和为x

区间和

• 一个非单调数组找出一段区间的和为x（寻找前缀和数组差为x的数对）

乘积统计

• 给出两个长度为n的数组a,b,从中各取出一个数乘起来，可以得到n^2个乘积，求这些乘积里小于等于x的个数

维护两个指针,单向移动指针维护和 /差

分治

• 分治思想

  • 将较大规模的问题分解成较小规模的问题

  • 当规模足够小时直接解决，不够小时再分治

  • 归并排序

void gsort(int l,int r){
    int mid=(l+r)/2;
    if(l+1==r){
        if(a[l]>a[r]) swap(a[l],a[r]);
    }
    else if(l==r) return;
    else{
        gsort(l,mid);
        gsort(mid+1,r);
        int tmp[N],p=l,q=mid+1,i=l;
        while(p<=mid&&q<=r){
            if(a[p]<=a[q]) tmp[i++]=a[p++];
            else tmp[i++]=a[q++];
        }
        while(p<=mid) tmp[i++]=a[p++];
        while(q<=r) tmp[i++]=a[q++];
        for(int i=l;i<=r;i++) a[i]=tmp[i];
    }
}

逆序对

在一个序列中，如果一个数大于它后面的某个数，那么构成一个逆序对

用分治思想解决