分治法求一组数中最大的两个数和最小的两个数代码C++

以下是使用分治法求一组数中最大的两个数和最小的两个数的C++代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int a[MAXN], max1, max2, min1, min2;

void dc(int l, int r) {
    if (l == r) {
        max1 = max2 = a[l];
        min1 = min2 = a[l];
        return;
    }
    if (l + 1 == r) {
        if (a[l] < a[r]) {
            max1 = a[r], max2 = a[l];
            min1 = a[l], min2 = a[r];
        } else {
            max1 = a[l], max2 = a[r];
            min1 = a[r], min2 = a[l];
        }
        return;
    }
    int mid = (l + r) >> 1;
    dc(l, mid);
    int tmpmax1 = max1, tmpmax2 = max2, tmpmin1 = min1, tmpmin2 = min2;
    dc(mid + 1, r);
    if (max1 < tmpmax1) {
        max2 = max1;
        max1 = tmpmax1;
    } else if (max1 < tmpmax2) {
        max2 = max1;
        max1 = tmpmax2;
    } else if (max2 < tmpmax1) {
        max2 = tmpmax1;
    } else if (max2 < tmpmax2) {
        max2 = tmpmax2;
    }
    if (min1 > tmpmin1) {
        min2 = min1;
        min1 = tmpmin1;
    } else if (min1 > tmpmin2) {
        min2 = min1;
        min1 = tmpmin2;
    } else if (min2 > tmpmin1) {
        min2 = tmpmin1;
    } else if (min2 > tmpmin2) {
        min2 = tmpmin2;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    dc(1, n);
    printf("max1 = %d, max2 = %d, min1 = %d, min2 = %d\n", max1, max2, min1, min2);
    return 0;
}

首先，定义了一个 `dc` 函数，用于分治求解。

当区间长度为1时，最大值和最小值都是该元素本身。

当区间长度为2时，比较两个元素，求出最大值和次大值，以及最小值和次小值。

当区间长度大于2时，将区间分成两部分，递归求解左右两部分的最大值、次大值、最小值、次小值，然后将左右两部分的结果组合成整个区间的结果。

在求解过程中，使用四个变量 `max1`、`max2`、`min1`、`min2` 分别表示当前区间的最大值、次大值、最小值、次小值。在递归返回时，将左右两部分的最大值、次大值、最小值、次小值合并成整个区间的最大值、次大值、最小值、次小值。