热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

「小顶/大顶堆」找第k大数,找第k小丑数,找杨氏矩阵第k小数

找第k小丑数:用小顶堆每次取顶x,判断set[]是否已有该数x,若无,把x加入set[],并把x*a,x*b,x*c加入堆。第k进入set[]的是第k大丑数。找第k大数:如

找第k小丑数:  

用小顶堆每次取顶x,判断set[]是否已有该数x,若无,把x加入set[],并把x*a,x*b,x*c 加入堆。第k进入set[]的是第k大丑数。


找第k大数:

如果所有数字可以用堆装,那么放入大顶堆里面。取到第k个就是了。

否则需要对所有数字分段计数。


给定递增的数组 a[m] 和 b[n],找第k小的a[i] + b[j]:

这等价于从一个特殊的杨氏矩阵Mat[ m ][ n ]中找第k小数, Mat[i][j] = a[i] + b[j],

杨氏矩阵 满足特征 a[i][j] <= a[i+1][j], a[i][j]<= a[i][j+1]

实现方法: 

宽搜法(bfs), 每次访问到Mat[i][j]的时候,接下来判断Mat[i][j+1] 和Mat[i+1][j]是否在小顶堆里,如果不在,将其插入到小顶堆。

时间复杂度: O(K*lg K )

#include 
#include
#include
#include
#include
using namespace std;
int m=1000, n=1000;
int a[1000], b[1000];

int lst[1000];
typedef pair Pair;
struct cmp{
bool operator ()(const Pair &l, const Pair &r){
bool t=a[l.first]+ b[l.second] return !t;//@error: if return t, then bigger pairs come top in priority_queue ! but we need smaller ones.
}
}cmper;
int getK(int k){//find k-th smallest a[i]+b[j]
assert(k <= m*n);
memset(lst, -1, m*sizeof(int));
/*if(m<=0 || n<=0){ // no need
return m<=0? b[k]: a[k];
}*/
priority_queue, cmp> q; //small top queue

Pair p(0, 0);
q.push(p);
lst[0]=0;
int num=0;
while(!q.empty()){
Pair p=q.top(); q.pop();
int i=p.first, j=p.second;
num++;
if(num == k) return a[i]+b[j];
if(i+1lst[i+1]){
lst[i+1]=j, q.push(Pair(i+1, j));
}
if(j+1lst[i]){
lst[i]=j+1, q.push(Pair(i, j+1));
}
}
assert(0);
return -1;
}
int main(){
cin>>m>>n;
for(int i=0; i cin>>a[i];
}
for(int j=0; j cin>>b[j];
}
int k; cin>>k;
cout< return 0;
}



推荐阅读
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • IhaveconfiguredanactionforaremotenotificationwhenitarrivestomyiOsapp.Iwanttwodiff ... [详细]
  • 李逍遥寻找仙药的迷阵之旅
    本文讲述了少年李逍遥为了救治婶婶的病情,前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵,有些方格内有怪物,有些方格是安全的。李逍遥需要避开有怪物的方格,并经过最少的方格,找到仙药。在寻找的过程中,他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]
  • 本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes,通过状压和spfa算法解决了这个问题。给定一个有向图,求在不超过m步的情况下,能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 本文讨论了一个数列求和问题,该数列按照一定规律生成。通过观察数列的规律,我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和,其中f[i]表示数列中有i个数字。根据参考的思路,我们可以将算法的时间复杂度控制在O(n),即计算到5e5即可满足1e9的要求。 ... [详细]
  • Java太阳系小游戏分析和源码详解
    本文介绍了一个基于Java的太阳系小游戏的分析和源码详解。通过对面向对象的知识的学习和实践,作者实现了太阳系各行星绕太阳转的效果。文章详细介绍了游戏的设计思路和源码结构,包括工具类、常量、图片加载、面板等。通过这个小游戏的制作,读者可以巩固和应用所学的知识,如类的继承、方法的重载与重写、多态和封装等。 ... [详细]
  • 向QTextEdit拖放文件的方法及实现步骤
    本文介绍了在使用QTextEdit时如何实现拖放文件的功能,包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数,并结合QMimeData和QUrl等类,可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]
  • 本文介绍了一个题目的解法,通过二分答案来解决问题,但困难在于如何进行检查。文章提供了一种逃逸方式,通过移动最慢的宿管来锁门时跑到更居中的位置,从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况,并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后,文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]
  • 先看官方文档TheJavaTutorialshavebeenwrittenforJDK8.Examplesandpracticesdescribedinthispagedontta ... [详细]
  • JDK源码学习之HashTable(附带面试题)的学习笔记
    本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记,包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货,并附带了其他相关主题的学习笔记。 ... [详细]
  • 重入锁(ReentrantLock)学习及实现原理
    本文介绍了重入锁(ReentrantLock)的学习及实现原理。在学习synchronized的基础上,重入锁提供了更多的灵活性和功能。文章详细介绍了重入锁的特性、使用方法和实现原理,并提供了类图和测试代码供读者参考。重入锁支持重入和公平与非公平两种实现方式,通过对比和分析,读者可以更好地理解和应用重入锁。 ... [详细]
  • 本文介绍了在Android开发中使用软引用和弱引用的应用。如果一个对象只具有软引用,那么只有在内存不够的情况下才会被回收,可以用来实现内存敏感的高速缓存;而如果一个对象只具有弱引用,不管内存是否足够,都会被垃圾回收器回收。软引用和弱引用还可以与引用队列联合使用,当被引用的对象被回收时,会将引用加入到关联的引用队列中。软引用和弱引用的根本区别在于生命周期的长短,弱引用的对象可能随时被回收,而软引用的对象只有在内存不够时才会被回收。 ... [详细]
  • STL迭代器的种类及其功能介绍
    本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系,并详细描述了各个迭代器的功能和使用方法。其中,输入迭代器用于从容器中读取元素,输出迭代器用于向容器中写入元素,正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]
  • 本文介绍了一道经典的状态压缩题目——关灯问题2,并提供了解决该问题的算法思路。通过使用二进制表示灯的状态,并枚举所有可能的状态,可以求解出最少按按钮的次数,从而将所有灯关掉。本文还对状压和位运算进行了解释,并指出了该方法的适用性和局限性。 ... [详细]
author-avatar
Yvette-XY
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有