`
128kj
  • 浏览: 603943 次
  • 来自: ...
社区版块
存档分类
最新评论

大(小)顶堆练习:POJ 1442

阅读更多
POJ1442题意:
   ADD(a)表示向集合中增加元素a,get表示取出第k小元素,k根据get出现的次数不断变化,出现多少次取第几小数。
样例:

Sample Input

7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Sample Output

3
3
1
2

解释:
输入 n = 7 m =4,然后第一行输入n个数,然后另一行输入m个数

index = 1

1:输出n个数中前1个数中的第Index(1)小值

index=2

2:输出n个数中前2个数中的第index(2)小值

index=3

6:输出n个数中前6个数中的第index(3)小值

index=4

6:输出n个数中前6个数中的第index(4)小值


输入保证m个数单调递增

题解:每次取第k小元素,k不断更新。使用两个堆,来完成。 小顶堆负责,选出最小的元素,大顶堆负责,选出k个元素中最大的元素,即第k小元素


import java.util.Scanner;

  public class Main{
   int tree1[];//大顶堆   
   int k1;  
   int tree2[];//小顶堆   
   int k2;  
   int M, N;  
   int A[];  
  
  public Main(){
   }

  //tree:大顶堆
  void build1(int[] tree, int k)  //从下标k开始,大堆向上调整到根
  {  
    int p = k;  
    while(p != 1)  
    {  
        if(tree[p] > tree[p / 2])  //如果大于父亲
        {  
            int temp = tree[p];  //交换
            tree[p] = tree[p / 2];  
            tree[p / 2] = temp;  
        }  
        p = p / 2;  //指向父亲
    }  
}  
  //tree:小顶堆
void build2(int[] tree, int k)  //从k开始,小堆向上调整
{  
    int p = k;  
    while(p != 1)  
    {  
        if(tree[p] < tree[p / 2])  //如果小于交亲
        {  
            int temp = tree[p];  //交换
            tree[p] = tree[p / 2];  
            tree[p / 2] = temp;  
        }  
        p = p / 2;  //指向父亲
    }  
}  
  
//tree:大顶堆
void update1(int[] tree, int k){//向下调整大顶堆的根.  
    int p = 1;  //指向根
    while(2 * p <= k)  
    {  
        int son;  
        if(2 * p == k || tree[2 * p] > tree[2 * p + 1])  
            son = 2 * p;  
        else  
            son = 2 * p + 1;  
        if(tree[p] < tree[son])  //如果父节点的值小于左右儿子中最大者,交换
        {  
            int temp = tree[p];  
            tree[p] = tree[son];  
            tree[son] = temp;  
        }  
        p = son;  //指向儿子节点
    }  
}  
  
//tree:小顶堆
void update2(int[] tree, int k)  //向下调整小顶堆的根,直到k
{  
    int p = 1;  
    while(2 * p <= k)  
    {  
        int son;  
        if(2 * p == k || tree[2 * p] < tree[2 * p + 1])  //取左右儿子中的较小者
            son = 2 * p;  
        else  
            son = 2 * p + 1;  
        if(tree[p] > tree[son])  //如果父节点的值大于左右儿子中最大者,交换
        {  
            int temp = tree[p];  
            tree[p] = tree[son];  
            tree[son] = temp;  
        }  
        p = son;  
    }  
}  
  
  public void  go(){  
   Scanner in=new Scanner(System.in);
    while(in.hasNext())  
    {  
     M=in.nextInt();
     N=in.nextInt();

     A=new int[M+1];
     tree1=new int[M+1];
     tree2=new int[M+1];
     for(int i = 1; i <= M; ++ i)  
            A[i]=in.nextInt();//将M个元素全部读入A
  
        int pre = 0;  
        k1 = k2 = 0;  
        for(int i = 1; i <= N; ++ i)  //共N轮
        {  
            int a=in.nextInt();  
            for(int j = pre + 1; j <= a; ++ j)  //从A中读入前a个元素到tree2
            {  
                tree2[++k2] = A[j];  //读一个,调整一个
                build2(tree2, k2);  //构建tree2使之成为最小堆
                  
            }  
            pre = a;  
            tree1[++ k1] = tree2[1];  //将最小堆的堆顶元素放入tree1中
            build1(tree1, k1);  //构建tree1使之成为最大堆
            tree2[1] = tree2[k2 --];  //删除最小堆的堆顶元素,最小堆的最后一个元素放到堆顶
            update2(tree2, k2);  //调整,使tree2成为小顶堆
            while(k2 != 0 && tree1[1] > tree2[1])  
            {  
                int temp = tree1[1];  
                tree1[1] = tree2[1];  
                tree2[1] = temp;  
                update1(tree1, k1);  //调整,使tree1成为大顶堆
                update2(tree2, k2);  //调整,使tree2成为小顶堆
            }  
            System.out.printf("%d\n", tree1[1]);  
        }         
    }
  }  
    
  public static void main(String args[]){
       Main ma=new Main();
       ma.go();
  }
}
分享到:
评论

相关推荐

    大顶堆应用:POJ2010

    标题“大顶堆应用:POJ2010”指的是一个关于大顶堆算法在解决实际问题中的应用,特别是针对编程竞赛网站POJ(Programming Online Judge)上的问题2010。大顶堆是一种特殊的完全二叉树,其每个节点的值都大于或等于其...

    堆排序练习:POJ 2388

    标题“堆排序练习:POJ 2388”指的是一个关于使用堆排序算法解决编程竞赛问题的实践案例。在编程竞赛中,如POJ(Programming Online Judge)平台上的问题2388,参赛者经常需要高效地解决排序问题,而堆排序作为一种...

    凸包练习: POJ 2187(JAVA)

    【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    树状数组练习:POJ 3067

    【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...

    直接插入排序练习:POJ 2388

    这个练习题目,"POJ 2388",显然是通过编程实现直接插入排序来解决一个特定的问题。在这个问题中,我们需要理解直接插入排序的机制,并能用Java语言编写出高效的代码。 直接插入排序的基本步骤如下: 1. 从第二个...

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

    ACM常用算法及其相应的练习题 (2).docx

    (4) 哈希表和二分查找等高效查找法:poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503 (5) 哈夫曼树:poj3253 (6) 堆 (7) trie树:poj2513 四、简单搜索 本部分涵盖了简单搜索,包括深度优先搜索、广度优先...

    ACMer需要掌握的算法讲解 (2).docx

    * POJ3109、POJ1478、POJ1462、POJ2729、POJ2048、POJ3336、POJ3315、POJ2148、POJ1263 八、附录 * ACM算法列表 + 哈希表、哈希数组 + 堆、优先队列 + 双端队列可并堆左偏堆 + Treap伸展树并查集 + 集合计数...

    ACM常用算法及其相应的练习题 (2).pdf

    例题:poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:最小生成树算法是指在图中寻找最小的生成树的算法。例题:poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:拓扑排序是指对有向...

    ACM常用算法及其相应的练习题.docx

    + poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    POJ(Peking University Online Judge)是一个知名的在线编程评测平台,提供了大量的编程题目供用户练习。这些题目按照不同的算法和技术进行了分类,以便用户能够有针对性地进行学习和提高。 ### 一、算法: #### ...

    滚动数组应用:POJ 1159

    标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...

    ACM 题型

    - 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...

    田忌赛马: POJ 2287(贪心解法)

    《田忌赛马:POJ 2287 贪心解法解析》 在计算机科学领域,算法是解决问题的核心。"田忌赛马"这个题目来源于古代中国的一个著名故事,而在这个故事的基础上,被引入到了编程竞赛的场景中。POJ(Programming Online ...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    极角排序:POJ 1696(叉积+深搜)

    夹角越小,排序位置越靠前。在实际操作中,为了避免角度比较的复杂性,通常会转换为比较向量的叉积,因为两个向量的叉积与它们构成的角度的正弦值成比例。 深度优先搜索在此问题中的应用可能是在构建某种搜索树或者...

    ACM 新手指南 PKU 题目分类

    - 示例题目:POJ 3349, POJ 3274, POJ 2151, POJ 1840, POJ 2002, POJ 2503 ##### 2. 图算法 - **最短路径**:包括迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)等,适用于求解两点之间的最短...

    acm poj300题分层训练

    poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...

Global site tag (gtag.js) - Google Analytics