竞赛算法(2) 排序, 查找

快速排序#

基于分治思想, 对于每个区间将其分为较小的一段和较大的一段, 较小段的最大值小于等于较大段的最小值.

快速排序的步骤

选定基准值x, 将某个区间分为小于等于x的部分和大于x的部分, 当x靠近中位数时分治效果较为理想. 通常随机选取区间中的某个数.

使用双指针i, j. 其中i从前往后遍历, j从后往前遍历.

保证i遍历过的部分都是小于等于x的, j遍历过的都是大于x的.

如果i处大于x, j处小于等于x, 并且i在j前面, 交换两处的数字, 并移动i和j

如果i不在j前面, 说明已经遍历完毕, break.

递归处理左右两段.

1
void qks(vector<int>& arr, int l, int r) {
2
    if (l >= r) return;
3
    int x = arr[(l + r) / 2];
4
    int i = l - 1;
5
    int j = r + 1;
6
    while (i < j) {
7
        do i++; while (arr[i] < x);
8
        do j--; while (arr[j] > x);
9
        if (i < j) swap(arr[i], arr[j]);
10
    }
11
    qks(arr, l, j);
12
    qks(arr, j + 1, r);
13
}

归并排序#

同样基于分治思想, 见算法导论.

1
void mgs(vector<int>& arr, int l, int r) {
2
    static vector<int> tmp(arr.size());
3
    if (l >= r) return;
4

5
    int mid = (l + r) / 2;
6
    mgs(arr, l, mid), mgs(arr, mid + 1, r);
7

8
    int i = l, j = mid + 1, k = 0;
9
    while (i <= mid && j <= r) {
10
        if (arr[i] <= arr[j]) {
11
            tmp[k++] = arr[i++];
12
        }
13
        else {
14
            tmp[k++] = arr[j++];
15
        }
16
    }
17
    while (i <= mid) {
18
        tmp[k++] = arr[i++];
19
    }
20
    while (j <= r) {
21
        tmp[k++] = arr[j++];
22
    }
23

24
    for (i = l, k = 0; i <= r; i++, k++) {
25
        arr[i] = tmp[k];
26
    }
27
}

归并排序用于求逆序对#

1
long long ans = 0;
2
void mgs(vector<int>& arr, int l, int r) {
3
    static vector<int> tmp(arr.size());
4
    if (l >= r) return;
5

6
    int mid = (l + r) / 2;
7
    mgs(arr, l, mid), mgs(arr, mid + 1, r);
8

9
    int i = l, j = mid + 1, k = 0;
10
    while (i <= mid && j <= r) {
11
        if (arr[i] <= arr[j]) { // 注意这里必须是小于等于
12
            tmp[k++] = arr[i++];
13
        }
14
        else {
15
            tmp[k++] = arr[j++];
16
            ans += mid - i + 1; // 添加的一行
17
        }
18
    }
19
    while (i <= mid) {
20
        tmp[k++] = arr[i++];
21
    }
22
    while (j <= r) {
23
        tmp[k++] = arr[j++];
24
    }
25

26
    for (i = l, k = 0; i <= r; i++, k++) {
27
        arr[i] = tmp[k];
28
    }
29
}

二分查找#

1
bool check(int a);
2
void bs(const vector<int>& arr) {
3
    int n = arr.size();
4
    int l = -1;
5
    int r = n;
6
    while (r - l > 1) {
7
        int mid = (l + r) / 2;
8
        if (check(arr[mid])) {
9
            l = mid;
10
        }
11
        else {
12
            r = mid;
13
        }
14
    }
15
    return;
16
}

1
// 实数域二分
2
const double PCS = 1e-7;
3
bool check(double a);
4
double bs(double n, double l, double r) {
5
    while (r - l > PCS) {
6
        double mid = (l + r) / 2;
7
        if (check(mid)) {
8
            l = mid;
9
        }
10
        else {
11
            r = mid;
12
        }
13
    }
14
    return l;
15
}

三分法#

求函数的极值. 结论: 如果若干个函数均为单极小值函数, 则他们取max也是单极小值函数. 例题: 1730B 285083A

01分数规划#

形式化表述: 给定两个数组A, B. 求一组 $w_i\in \set{0, 1}$ , 最小化或最大化 $\frac{\sum a_iw_i}{\sum b_iw_i}$ .

通俗地讲, 这相当于每个物品有两个权值a, b. 取若干个物品, 求a的总和与b的总和的比值.

这类问题通常可以用二分法来解决. 对于每个预测值mid, 我们应该考虑 $\sum a_iw_i$ 与 $\sum b_iw_i$ 的比值是否大于等于mid. 这等价于求某个子集使得 $\sum (a_i - mid \times b_i) \ge 0$ . 求出左式最大值即可.

例题: 285069A 285069C(nth_element的用法: nth_element(first, nth, last), 其中first, nth, last均为迭代器, 这个函数保证nth位置的数值准确, nth前全部小于nth, nth后全部大于nth. 平均O(n)的复杂度)