跳转至

排序-RMQ

106 动态中位数

排序 + Heap (对顶堆)

分析:

维护特征:

  1. 上面所有元素 >= 下面所有元素
    1. 这样才能确保数值关系 (中位数的必要条件)
  2. 下面的个数 最多比 上面的个数 多1
    1. 这样才能确保是第 \(i / 2\) 个位置 (中位数的必要条件)
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;

int main()
{
    int T; //T为数据集个数
    scanf("%d", &T);

    while (T -- )
    {
        int id, n;
        scanf("%d%d", &id, &n);
        printf("%d %d\n", id, n + 1 >> 1); //输出数据集编号和中位数个数(即奇数位个数)


        priority_queue<int> down; //大根堆
        priority_queue<int, vector<int>, greater<int>> up; //小根堆

        int cnt = 0; //用于分隔输出,每十个数一行
        for (int i = 0; i < n; i ++ )
        {
            int x;
            scanf("%d", &x);

            if (down.empty() || x <= down.top()) down.push(x);  //下面为空或x小于下方堆顶,则将x插入大根堆
            else up.push(x);

            //如果有偶数个数,上面和下面一样多,如果有奇数个数,则下面比上面多一个
            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();   //下面多了挤一个放上面
            if (up.size() > down.size()) down.push(up.top()), up.pop(); //上面多了挤一个放下面

            if (i % 2 == 0) //每插入奇数个数就输出一次中位数
            {
                printf("%d ", down.top());
                if ( ++ cnt % 10 == 0) puts("");
            }
        }

        if (cnt % 10) puts(""); //不是整十数行,就手动输入一个空行
    }
    return 0;
}

107 超快速排序

求 “逆序对” 数量

在这个问题中，您必须分析特定的排序算法 -- 超快速排序。

该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>

typedef long long LL;

const int N = 500010;

int n;
LL q[N], w[N];

LL merge_sort(int l, int r) // 求“逆序对”的模板
{
    if (l == r) return 0;

    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            w[k ++ ] = q[j ++ ];
        }
    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];

    return res;
}

int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

        printf("%lld\n", merge_sort(0, n - 1));
    }

    return 0;
}

1273 天才的记忆

RMQ 算法: 只能查询, 不能修改 (仅静态查询)

给你一大串数字（编号为 1 到 N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 M 个询问，每次询问就给你两个数字 A,B，要求你瞬间就说出属于 A 到 B 这段区间内的最大数。

纯模板, 分析:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

void init()
{
    for (int j = 0; j < M; j ++ ) // 枚举区间长度
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ ) // 枚举起点, 注意边界
            if (!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r)
{
    /*
    |-----------------len-------------------|
    |-------------2^k-----------|
                |------------2^k------------|
    */
    int len = r - l + 1;
    int k = log(len) / log(2);

    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    init();

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}