• 「二叉堆」序列


    序列

    原题链接:序列

    题目大意

    给你(m)行,每行(n)个数,让你从(m)行中每行选一个数组成一个长度为(n)的序列,并且一共会组成(n^m)个序列,这些序列中的数求和,让你求出前(n)个最小序列。

    题目题解

    很经典的题,当作典型模型可以记住

    模型:分组,先考虑(m = 2)的情况,我们设第一组为(a_n) 第二组为(b_n) 我们将这两组数单独排序,那么我们可能会得到这样一个错误的写法,就是(a_1 + b_1)是最小 (a_2 + b_2) 是次小,这显然是错误的,为何错误?这里不证

    再考虑一下,似乎可以转化成下面这个竖式

    (a_1 + b_1)(a_1 + b_2)(a_1 + b_3) ... (a_1 + b_n)

    (a_2 + b_1)(a_2 + b_2)(a_2 + b_3) ... (a_2 + b_n)

    ....

    (a_n + b_1)(a_n + b_2)(a_n + b_3) ... (a_n + b_n)

    首先每组的最小值一定是第一个,其次是第二个,每次我们选择最小的加入我们的答案

    但是这仅是(m = 2)的情况,我们是否可以将所有情况套在这上面?答案是可以的,只要我们将(a_n)定义为我们当前得到的(n)个最大值,我们将(b_n)定义为当前我们读入的(m)行的话,就可以了,维护用小根堆维护

    代码如下

    //#define fre yes
    
    #include <queue>
    #include <vector>
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    
    typedef std::pair<int, int> PII;
    const int N = 2005;
    int a[N], b[N], c[N];
    
    int n, m;
    
    void merge() {
        std::priority_queue<PII, std::vector<PII>, std::greater<PII> > heap;
        for (int i = 1; i <= n; i++) heap.push({a[1] + b[i], 1});
        for (int i = 1; i <= n; i++) {
            PII t = heap.top();
            heap.pop();
            int s = t.first, p = t.second;
            c[i] = s;
            heap.push({s - a[p] + a[p + 1], p + 1});
        }
        
        for (int i = 1; i <= n; i++) {
            a[i] = c[i];
        }
    }
    
    int main() {
        static int T;
        scanf("%d", &T);
        while(T--) {
            scanf("%d %d", &m, &n);
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
            } std::sort(a + 1, a + 1 + n);
            
            for (int i = 1; i < m; i++) {
                for (int j = 1; j <= n; j++) {
                    scanf("%d", &b[j]);
                } merge();
            }
            
            for (int i = 1; i <= n; i++) {
                printf("%d ", a[i]);
            } puts("");
        } return 0;
    }
    
  • 相关阅读:
    正交矩阵(部分转载)
    向量的点乘和叉乘
    随机森林
    PCA和LDA
    SIFT和SURF特征(草稿)
    12-赵志勇机器学习-Label_Propagation
    11-赵志勇机器学习-DBSCAN聚类
    09-赵志勇机器学习-k-means
    10-赵志勇机器学习-meanshift
    09-numpy-笔记-repeat
  • 原文地址:https://www.cnblogs.com/Nicoppa/p/11536934.html
一二三 - 开发者的网上家园