超快速排序

题意

通过交换相邻两个数，来给序列排序。求交换次数。

思考

就是求逆序对的个数，用归并排序求。

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;
}

动态中位数

题意

一个一个输入数，但总个数为奇数时输出它们的中位数。

思考

对顶堆：一个大根堆 + 一个小根堆。

需要满足性质：

  • 大根堆的所有值都小于小根堆。
  • 输入为偶数，上下堆的元素数量相同。输入为奇数，下面比上面多1。

注意：比较上下两个优先队列的值的时候，不能使用down.size()-up.size()>1,因为size()返回的是无符号长整数，会出问题。

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;
}

七夕祭

题意

思考

1