首页 > 技术文章 > 南大算法设计与分析课程OJ答案代码(3)

likaiming 2018-04-25 21:36 原文

 

问题 A: 动态中位数问题

时间限制: 1 Sec  内存限制: 8 MB
提交: 866  解决: 102
提交 状态 算法问答 

题目描述

输入一组整数a1, a2, …, an ,每输入一个整数,输出到此时为止的中位数。

中位数定义:如果数串的大小是偶数 2j,中位数是从小到大排列的第 j 个数;如果数串的大小是奇数 2j+1,中位数是从小到大排列的第 j+1 个数。

输入

一组整数,数字和数字之间以空格隔开。

输出

一组整数,数字和数字之间以空格隔开。最后一个数后面也有空格。

第 i 个输出的整数,是前 i 个输入的中位数。

样例输入

-18 -2 14 -20 -6 7 2 14 11 6 

样例输出

-18 -18 -2 -18 -6 -6 -2 -2 2 2 

提示

时间复杂度请不要超过O(nlogn)。
由于输入输出的量会比较大,因此推荐使用c语言中的scanf和printf函数来进行输入输出,能比c++中cin和cout节省许多时间。

这里本来有一行提示,但是由于老师上课不小心说漏嘴了,于是助教狠心地把它注释掉了 ;

/*在处理该问题时,堆结构也许能给你带来意想不到的帮助。*/

 答案

比较尴尬,最近一忙就忘记做了,所以答案没有经过oj测试,仅供参考(但测试用例一遍过了)

思路就是维护一个mid值、最大堆(存放比mid小的值)、最小堆(存放比mid大的值),每次读入一个数,根据两边堆的大小来判断当前值,具体怎么判断见代码注释,代码中有关STL中堆的使用操作就不多数了,自行查阅。

代码在VS2017上运行,在读入输出部分可能需要更改一下,scanf_s改scanf?

int main()
{
    vector<int> heap_small;    //这应该是个最大堆,存放着比mid小的元素
    vector<int> heap_big;    //这应该是个最小堆,存放着比mid大的元素
    int mid =0;
    scanf_s("%d",&mid);
    printf("%d ",mid);
    int temp = 0;
    while (scanf_s("%d",&temp)!=EOF) {
        if (temp < mid) {
            if (heap_small.size() == heap_big.size()) {
                //左侧和右侧一样大,将mid放入heap_big中,temp放入heap_small中,然后从heap_small选一个最大的作为mid
                heap_big.emplace_back(mid);
                push_heap(heap_big.begin(), heap_big.end(), [](int a, int b) {return b < a; });
                heap_small.emplace_back(temp);
                push_heap(heap_small.begin(),heap_small.end());
                pop_heap(heap_small.begin(), heap_small.end());
                mid = heap_small.back();
                heap_small.pop_back();
            }else if (heap_small.size() == heap_big.size() - 1) {
                //右侧比左侧多一个,将temp放入heap_small中,然后mid还是为中位数
                heap_small.emplace_back(temp);
                push_heap(heap_small.begin(), heap_small.end());
            }else {
                //左侧比右侧多一个的情况应该不会出现
                cout << "wrong" << endl;
            }
        }
        else {
            if (heap_small.size() == heap_big.size()) {
                //左侧和右侧一样大,将temp放入heap_big中,mid还是中位数
                heap_big.emplace_back(temp);
                push_heap(heap_big.begin(), heap_big.end(), [](int a, int b) {return b < a; });
            }
            else if (heap_small.size() == heap_big.size() - 1) {
                //右侧比左侧多一个,将mid放入heap_small中,然后将temp放入heap_big中,然后从heap_big选一个最小的作为mid
                heap_small.emplace_back(mid);
                push_heap(heap_small.begin(), heap_small.end());
                heap_big.emplace_back(temp);
                push_heap(heap_big.begin(), heap_big.end(), [](int a, int b) {return b < a; });
                pop_heap(heap_big.begin(), heap_big.end(), [](int a, int b) {return b < a; });
                mid = heap_big.back();
                heap_big.pop_back();
            }
            else {
                //左侧比右侧多一个的情况应该不会出现
                cout << "wrong" << endl;
            }
        }
        printf("%d ",mid);
    }
return 0;
}

 

问题 B: 非完美二叉树的高度与直径

时间限制: 2 Sec  内存限制: 3 MB
提交: 249  解决: 95
提交 状态 算法问答 

题目描述

记T为一棵二叉树,树中共有n个节点。

定义根节点的深度为0,其余节点的深度为其父节点的深度加1。T的高度定义为其叶节点深度的最大值。

定义树中任意两点a和b之间的距离为其间最短简单路径的长度。T的直径定义为T中所有点对间距离的最大值。

输入一棵二叉树T,请计算它的高度和直径。

输入

输入共三行。

第一行输入n的值,表示树中结点的总个数。

第二行为树的前序遍历表示,每个节点之间用空格隔开。

第三行为树的中序遍历表示,每个节点之间也用空格隔开。

输出

输出共三行。
第一行需要大家输出一行字符串,它是“我已阅读关于抄袭的说明”的英文翻译,即:"I have read the rules about plagiarism punishment"。输出此行的提交我们将认为已经完全阅读并了解了“关于抄袭的说明”公告并同意关于抄袭的惩罚措施。
第二行输出树的高度。
第三行输出树的直径。



样例输入

10
0 1 9 3 8 4 2 7 5 6 
3 9 8 1 2 4 0 5 7 6 

样例输出

I have read the rules about plagiarism punishment
3
5

提示

分治算法可以在O(n)的时间内完成相应的计算。

答案

没法提交了,懒得写了,网上答案挺多的

推荐阅读