第一章 基础算法

1 快速排序算法

1.1 快速排序算法1.2 快速排序算法应用——查找数组中第k个数 2 归并排序算法

2.1 归并排序算法2.2 归并算法应用——逆序对的数量 3 二分查找算法

3.1 二分查找算法3.2 二分查找的应用——数的范围3.3 二分查找的应用——数的三次方根（浮点数的二分） 4 高精度计算

4.1 高精度计算——加法4.2 高精度计算——减法4.3 高精度计算——乘法4.4 高精度计算——除法 5 前缀和与差分

5.1 前缀和5.2 子矩阵的和——二维前缀和5.3 一维差分数组

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, j); // 注意这里的 j
    quick_sort(q, j+1, r);
}

int quick_sort(int q[], int l, int r, int k)
{
    if (l >= r) return q[l];
    
    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]);
    }
    
    if (j - l + 1 >= k) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
}

// 基于分治思想
void merge_sort(int q[], int l, int r) 
{
    if (l >= r) return;
    
    int mid = (l + r) >> 1;
    
    // 递归排序
    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];
}

typedef long long LL;

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;
    
    int mid = (l + r) >> 1;
    
    LL res = 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 {
            // 排序后第一个序列中有几个大于 a[j]
            // 排序后两个子序列都是有序的！
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    
    for (int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
    
    return res;
}

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

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}

#include 

using namespace std;

const int N = 10e5 + 10;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    
    while (m--)
    {
        int x;
        scanf("%d", &x);
        
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        
        if (q[l] != x) cout << "-1 -1" << endl;
        else 
        {
            cout << l << ' ';
            
            int l = 0, r = n - 1;
            while (l < r) 
            {
                int mid = (l + r + 1) >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            
            cout << l << endl;
        }
    }
    
    return 0;
}

#include 

using namespace std;

int main()
{
    double x;
    cin >> x;
    
    double l = -100, r = 100;
    while (r - l > 1e-8) // 经验值，这里保证要比结果的精度多两位更保险（结果是保留六位小数）
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    
    printf("%.6lfn", l);
    
    return 0;
}

#include 
#include 

using namespace std;

vector add(vector &A, vector &B) // 注意这里的引用
{
    vector C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10); // 这时的t代表着A+B后相应位上的值
        t /= 10; // 这时的t代表着进位值
    }
    
    //如果最后还有进位
    if (t) C.push_back(t);
    
    return C;
}

int main()
{
    string a, b;
    vector A, B;
    cin >> a >> b;
    
    // 将数按位存储到vector中
    // Tips：倒序存储，进位方便扩展
    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');
    
    auto C = add(A, B);
    
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout< 
4.2 高精度计算——减法 
#include 
#include 

using namespace std;

// 比较两个字符串中存储数的大小
bool cmp(vector &A, vector &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;
}

vector sub(vector &A, vector &B)
{
    vector C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t; // 减去上一位借的一位
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10); // Tips：这里保证的加入C中的数都是正数
        if (t < 0) t = 1; // 需要借位
        else t = 0;
    }
    
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // Tips：去除尾部的零
    return C;
}

int main()
{
    string a, b;
    vector 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 C;
    
    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;
}
 
4.3 高精度计算——乘法 
#include 
#include 

using namespace std;

vector mul(vector &A, int b)
{
    vector C;
    
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ ) // 这里的t是用来处理最后算完后依然会有进位的情况！
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    
    while (C.size()  > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    vector A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    
    auto C = mul(A, b);
    
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    
    return 0;
}
 
4.4 高精度计算——除法 
#include 
#include 
#include 

using namespace std;

vector div(vector &A, int b, int &r) 
{
    vector C;
    r = 0;
    
    // 这个过程不理解的话去看视频
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    
    // 这里要翻转的原因是最后结果输出倒着输出的
    reverse(C.begin(), C.end());
    
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}

int main()
{
    string a;
    vector A;
    
    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    
    int r; // 余数
    auto C = div(A, B, r);
    
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    
    cout << endl << r << endl;
    
    return 0;
}
 
5 前缀和与差分 
5.1 前缀和 
#include 

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和数组初始化
    
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%dn", s[r] - s[l - 1]);
    }
    
    return 0;
}
 
5.2 子矩阵的和——二维前缀和 
#include 

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);
    
    // 前缀和数组的初始化        
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            
    while (q -- )
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        // 输出区间数组
        printf("%dn", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    
    return 0;
}
 
5.3 一维差分数组 
Tips：对差分数组求前缀和就是对应的前缀和数组，差分数组便于修改！本题的关键就在于，要在L、R之间的元素添加c，就是在原数组的查分数组里的L位置上的值加上c，在R+1的位置上减去c，这样求前缀和的时候，L及其之后的元素都会加上c，R+1及其之后的元素都会减去c，这样的前缀和数组即为所求。
 
#include 

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N]; // a是原数组，b是差分数组
// b[N]是a[N]的差分，a[N]是b[N]的前缀和

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    // 将原数组n个数插入进去构成差分数组
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
    
    // 这种调整使用差分数组，使时间复杂度从O(n)降到了O(1)
    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];
        printf("%d ", b[i]);
    }
    
    return 0;
}