精华内容
下载资源
问答
  • 我们可以推论出很多树的数学性质,例如上面描述的。 树的演化过程,其实是从一般到特殊化的过程,在演化出现各种特殊的树,来解决不同种类的问题。但是一颗一般化的树,在一些特殊...
  • 考虑一下维护中位数的过程原数组为A,找到不降数列为B当对于A前n个数已经好了最优解B[1…n],可知此时A被分成很多块,并被一些大顶堆记录,假设第i块有num个数,那么第i个堆维护这一块最小(num+1)/2个数,...

    我觉得我要改一下签名了……怎么会有窝这么啰嗦的人呢?

     

    做这题需要先学习左偏树左偏树的特点及其应用》 然后做一下POJ3666,这题的简单版。

    思路:

    考虑一下维护中位数的过程
    原数组为A,找到的不降数列为B
    当对于A的前n个数已经找好了最优解B[1…n],可知此时A被分成很多块,并被一些大顶堆记录,假设第i块有num个数,那么第i个堆维护这一块的最小的(num+1)/2个数,堆顶即为中位数。
    假设已经处理好前7个数,被分为两块 ([a,b],c,d) ([h,e],f) (每一块按升序排列,[]中的数是堆里面维护的。
    因为数列是不降的,所以b≤e
    当新添加一个元素的时候,设为x,如果x≤e,将需要向前合并。
    那么新的块应该是……分两种情况……
    1.x>h ([h,x],e,f)
    2.x<h ([x,h],e,f)

    设新的中位数是val=max(h, x)  分类讨论一下可以发现改变的值是(e-val)+(val-x)


    这里假设是([x,h],e,f)
    当h<b时,需要继续向前合并。
    合并之后是([x,h,a,b],c,d,e,f) (顺序已经不确定了,只能确定栈中元素和栈顶是b

    可以发现大小为偶数的块和偶数的块合并,合并后的堆不需要弹出元素。
    合并前([a,b],c,d) 的中位数是b ([x,h],e,f)的中位数是h, 合并后的中位数的b
    可知答案改变都是发生在集合([x,h],e,f)中的,我们又知道b≤e(上面提到过),那么很容易得到答案是不变哒!(就是把(h-x)+(h-h)+(e-h)+(f-h)变成了(b-x)+(b-h)+(e-b)+(f-b),值是一样的

    上面是偶数和偶数合并,继续讨论前一块奇数和后一块偶数合并。
    设前一块是([a,b],c) 中位数是b,后一块是([d,e],f,g)中位数是e,合并后不需要弹出,中位数是b,类似上面的情况,我们可以得出b≤f,所以答案仍然不变。

    前一块偶数,后一块奇数
    ([a,b],c,d)中位数是b ([e,f],g)中位数是f 合并后不需要弹出 中位数是b 其中(f<b≤g)
    那么答案由([e,f],g)的改变产生,f的左右两边是可以抵消掉的,改变只会因为f,改变的值是b-f

    前一块奇数,后一块奇数
    设前一块是([a,b],c) 中位数是b,后一块是([d,e],f,)中位数是e 其中e<b≤f
    合并后弹出元素b,中位数为max(a,e),设为val
    那么答案改变就是b-e


    到此,所有情况都讨论完了ˊ_>ˋ

    结论:当一个块和前面的块合并时,如果当前块的数量为偶数,答案不变,否则答案增加(前一块的中位数-当前块的中位数)

    代码:

    /*****************************************
    Problem: 3016        User: G_lory
    Memory: 12676K        Time: 1797MS
    Language: G++        Result: Accepted
    *****************************************/
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N = 2005;
    const int INF = 0x5f5f5f5f;
    typedef long long ll;
    
    struct LTree {
        int l, r, sz;
        int key, dis;
        bool operator<(const LTree lt) const {
            return key < lt.key;
        }
    } tr[N];
    int cnt_tr;
    
    int NewTree(int k) {
        tr[++cnt_tr].key = k;
        tr[cnt_tr].l = tr[cnt_tr].r = tr[cnt_tr].dis = 0;
        tr[cnt_tr].sz = 1;
        return cnt_tr;
    }
    
    int Merge(int x, int y) {
        if (!x || !y) return x + y;
        if (tr[x] < tr[y]) swap(x, y);
        tr[x].r = Merge(tr[x].r, y);
        if (tr[tr[x].l].dis < tr[tr[x].r].dis) swap(tr[x].l, tr[x].r);
        tr[x].dis = tr[tr[x].r].dis + 1;
        tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + 1;
        return x;
    }
    
    int Top(int x) {
        return tr[x].key;
    }
    
    void Pop(int &x) {
        x = Merge(tr[x].l, tr[x].r);
    }
    
    int root[N], num[N];
    void cal(int a[], int n, int ans[]) {
        int res;
        cnt_tr = res = 0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            root[++cnt] = NewTree(a[i]);
            num[cnt] = 1;
            while (cnt > 1 && Top(root[cnt]) < Top(root[cnt-1])) {
                cnt--;
                if (num[cnt+1]&1) res += Top(root[cnt]) - Top(root[cnt+1]);
                root[cnt] = Merge(root[cnt], root[cnt+1]);
                num[cnt] += num[cnt+1];
                while (tr[root[cnt]].sz*2 > num[cnt]+1) {
                    Pop(root[cnt]);
                }
                int now = Top(root[cnt]);
                
            }
            ans[i] = res;
        }
    }
    
    int a[N], b[N], c[N];
    int in[N][N], de[N][N];
    int dp[N][N];
    int main() {
        //freopen("in", "r", stdin);
        int n, k;
        while (~scanf("%d%d",&n, &k) && n) {
            for (int i = 1; i <= n; ++i) {
                scanf("%d", a+i);
                b[i] = a[i]-i;
                c[i] = -a[i]-i;
            }
            for (int i = 1; i <= n; ++i) {
                cal(c+i, n-i+1, de[i]+i);
                cal(b+i, n-i+1, in[i]+i);
            }
            for (int i = 1; i <= n; ++i) dp[0][i] = INF;
            for (int i = 1; i <= k; ++i) {
                dp[i][0] = 0;
                for (int j = 1; j <= n; ++j) {
                    dp[i][j] = INF;
                    for (int p = 0; p < j; ++p) {
                        dp[i][j] = min(dp[i][j], dp[i-1][p] + min(in[p+1][j], de[p+1][j]));
                    }
                }
            }
            printf("%d\n", dp[k][n]);
        }
        return 0;
    }

     

      

     

    转载于:https://www.cnblogs.com/wenruo/p/5798801.html

    展开全文
  • 3.5.4 在一个文件中有10G个整数,乱序排列,要求中位数。内存限制为2G。 3.5.5 时分秒针在一天之类重合多少次?(24小时) 3.5.6 将个集合合并成没有交集集合。 3.5.7 平面内有11个点,由它们连成48条...
  • 大话数据结构

    2018-12-14 16:02:18
    也就是在树的定义之还用到了树的概念,这是比较新的一种定义方法。 6.2.1结点分类 152 6.2.2结点间关系 152 6.2.3树的其他相关概念 153 6.3树的抽象数据类型 154 6.4树的存储结构 155 6.4.1双亲表示法 155 ...
  • LeetCode ...我们的 slogon 是: 只有熟练掌握基础的数据结构与算法,才能对复杂问题迎刃有余。...这是我将我的所有公开的算法资料整理的一个电子书,全部题目...0004. 寻找两个正序数组的中位数 0023. 合并 K ...
  • 摄像头.zip

    2019-07-23 23:33:32
    在原来程序也增加了很多算法包括十字、斜入十字、坡道等。改动比较大也有些地方,但是大体寻线补线思路还是学长。就像是一支树干我们只是修理了一些树枝、增加了一些树枝。让更繁茂。其实比赛快结束...
  • 要想学习和掌握它诸多新特性,只能从Oracle手册入手,而万页11g手册不免让人心存畏惧,从中挑出对新特性描述更需要一双“火眼金睛”。  好消息!在本书第1版出版时隔4年后,Thomas Kyte及时了解了大家这...
  • 51单片机自学笔记

    2016-07-27 22:24:19
    , 来自作者建议, 多找几本参考书,从中选择适合自己,不要一《51单片机自学笔记》看几天感觉难,就放弃了。, 一定要有电脑和实验板,无论书,如果不亲自调试程序,不用实验板做实验话,就不会对所学...
  • 列举了很多编程建议,其实就是告诉怎样去写好代码,你需要从能写代码(入门)过渡到会写代码,这本书值得一看。如果你编码经验比较少,那这边书你可以稍微往后延,因为看完了你可能没有感同身受。 《Java8 ...
  • 它本身就是一个完整 32 位的多用户任务操作 系统,因此不需要先安装 DOS 或其他操作系统(MS Windows, OS2, MINIX..)就可以进 行直接安装。 Linux最早起源是在1991年10月5日由一芬兰大学生Linux ...
  • 深入学习shell脚本艺术

    热门讨论 2011-02-22 04:01:01
    中文版版权由译者杨春敏和黄毅共同所有,在遵守英文版版权相应条款条件下,欢迎在保留本书译者名字和版权说明以非盈利方式自由发布此中文版,以盈利目的所有行为必须联系英文作者和两中文译者以获得许可。...
  • C、C++语言是IT行业主流编程语言,也是很多程序员必备软件基本功,是软件开发行业招聘考查重点。本书以流行面试题讲解为主要内容,介绍了C、C++语言基本概念,包括保留字、字符串、指针和引用、结构体、...
  •  本书作者是oracle资深dba,本书不仅融入了作者十年实战心得和工作经验,还提供了来自于工作现场大量实例,具有可操作性。..  本书可以作为数据库开发人员、数据库管理员、数据库初学者及其他数据库从业...
  • 学习Oracle时,很多书和资料都很有参考价值,特别是Oracle文档,更是全面地提供了我们想了解信息。但是文档没有实战用例,没有告诉我们哪些可行或者哪些不可行,什么情况下可行或者什么情况下不可行,为什么可行...
  •  相信很多对Oracle有一定经验DBA和我有同样感觉,RAC比普通Oracle更难入门。不仅因为比比皆是晦涩艰深术语,也不仅因为它覆盖技术领域太广,更主要是可用参考资料太少。我翻遍了所有能够获得书籍...
  • 我会从下图中的知识点去写这个系列,很多细节点,可能想得不是很完善,大家可以去【公众号】获取或者加我【微信】提意见(别忘记Star哟)。 原创文章每周最少两篇,公众号首发文章,【B站】首发视频,比博客早一到两...
  • 而此次主要是针对校园用户所设计网站,对于数据分类应该更多的考虑校园用户需求,例如二手书籍、二手数码等分类应该更加细致。本次设计主要难度在于数据详细分类,对于数据过滤必须要严谨,应当考虑...
  • -重新设计模拟树的下拉列表的实现,避免选中某项后的闪烁。 +2009-11-21 v2.1.5 +Tree优化。 -修正Expanded项和Checked项的状态在回发改变后不能保持的BUG。 -GetNodeById更名为FindNode,保持和...
  • ExtAspNet_v2.3.2_dll

    2010-09-29 14:37:08
    -重新设计模拟树的下拉列表的实现,避免选中某项后的闪烁。 +2009-11-21 v2.1.5 +Tree优化。 -修正Expanded项和Checked项的状态在回发改变后不能保持的BUG。 -GetNodeById更名为FindNode,保持和...
  • java 面试题 总结

    2009-09-16 08:45:34
    assertion(断言)在软件开发是一种常用调试方式,很多开发语言中都支持这种机制。在实现,assertion就是在程序中的一条语句,它对一个boolean表达式进行检查,一个正确程序必须保证这个boolean表达式值为...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

很多树的中位数怎么找