基础算法总结

排序

1. 快速排序

模板背住

void quick_sort(int a[], int start, int end){
    if(start >= end){
        return;
    }
    int left = start;
    int right = end;
    int pivot = a[start + (end - start) / 2];
    while(left <= right){
        while(left <= right && a[left] < pivot){
            ++left;
        }
        while(left <= right && a[right] > pivot){
            --right;
        }
        if(left <= right){
            swap(a[left], a[right]);
            ++left;
            --right;
        }
    }
    quick_sort(a, start, right);
    quick_sort(a, left, end);
}

2. 归并排序

模板背住

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e6 + 10;

int a[N], t[N];
int n;

void merge(int start, int mid, int end){
    int left = start;
    int right = mid + 1;
    int index = start;
    while(left <= mid && right <= end){
        if(a[left] <= a[right]){
            t[index++] = a[left++];
        }else{
            t[index++] = a[right++];
        }
    }
    while(left <= mid){
        t[index++] = a[left++];
    }
    while(right <= end){
        t[index++] = a[right++];
    }
    for(index = start; index <= end; ++index){
        a[index] = t[index];
    }
    return;
}

void merge_sort(int start, int end){
    if(start >= end){
        return;
    }
    int mid = start + (end - start) / 2;
    merge_sort(start, mid);
    merge_sort(mid + 1, end);
    merge(start, mid, end);
}

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

查找

1. 二分查找

模板背住

int binary_first(int a[], int target){
    int start = 0;
    int end = n - 1;
    while(start + 1 < end){ //使用这种不会出现边界问题
        int mid = start + (end - start) / 2;
        if(a[mid] < target){    //核心就是通过这几句控制指针的移动
            start = mid;
        }else{
            end = mid;
        }
    }
    // start 和 end 之中有一个是符合条件的
    // 如果想找第一个位置，可以先进行start的判断，后进行end的判断
    // 如果想找最后一个位置，可以先进行end的判断，后进行start的判断
    if(a[start] == target){
        return start;
    }
    if(a[end] == target){
        return end;
    }
    return -1;
}

2. 实数二分

将精度至少控制比题目要求大2位，实际上实数的二分就是不断逼近，得到一个近似解。

前缀和

实际上前缀和就是一种简单的动态规划思想的运用，前缀和算法一个巧妙的设计就是从数组1开始前缀判断，这样很好的避免了边界情况。前缀和的操作往往用于计算一个数组中某个区间的和。

差分

1. 一维差分

差分实际上是前缀和逆运算，求数组b使其满足其前缀和为a，即b[i] = a[i] - a[i - 1]。差分应用于给数组的某个区间加上某个数值。

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N];
int b[N];

void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main(void){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; ++i){
        insert(i, i, a[i]);
        //可以改为b[i] = a[i] - a[i - 1]
        //也可以模拟下insert的过程
        //a1 -a1 -a1 ...
        //a1 -a1+a2 -a1-a2 ...
        //a1 a2-a1 -a1-a2+a3 ...
    }

    while(m--){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for(int i = 1; i <= n; ++i){
        b[i] += b[i - 1];
    }

    for(int i = 1; i <= n; ++i){
        printf("%d ", b[i]);
    }

    return 0;
}

位运算

待补充

离散化

对离散化可以有如下的理解，离散化实际上就是对分散的数值建立到连续的一组整数的map。如题目中碰到的坐标，核心就是将所有离散的数值放在一个vector中，进行去重，得到的就是全部的不重复的离散坐标，然后利用二分查找查找出坐标在vector数组中的唯一位置，得到了唯一的位置之后。就能够使用前缀和、差分等算法了。

区间合并

区间合并就是类似于线段的合并，这类合并的题目往往就是排序加贪心，排序往往就是对首关键字或者次关键字进行排序。需要记牢排序的模板：

void merge_segment(vector<PII>& segs){
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for(auto seg : segs){
        //区间不能够合并时，对区间进行记录
        //首次更新区间时并不做记录
        if(ed < seg.first){  
            if(st != -2e9){
                res.push_back({st, ed});
            }
            st = seg.first, ed = seg.second;
        }else{
            ed = max(ed, seg.second);
        }
    }
    //防止只有一个区间 或者 最后一个区间被漏掉
    if(st != -2e9) res.push_back({st, ed});
    segs = res;
}

或许区间合并也能通过双指针去贪心（还没试过）