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

找第ｋ小丑数：　　

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

找第ｋ大数：

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

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

给定递增的数组 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 <iostream>
#include <string.h>
#include <queue>
#include <assert.h>
#include <map>
using namespace std;
int m=1000,n=1000;
int a[1000],b[1000];

int lst[1000];
typedef pair<int,int> Pair;
struct cmp{
	bool operator ()(const Pair &l,const Pair &r){
		bool t=a[l.first]+ b[l.second] < a[r.first]+ b[r.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<Pair,vector<Pair>,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+1<m && j>lst[i+1]){
			lst[i+1]=j,q.push(Pair(i+1,j));
                }
		if(j+1<n && j+1>lst[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<m; i++){
		cin>>a[i];
	}
	for(int j=0; j<n; j++){
		cin>>b[j];
	}
	int k; cin>>k;
	cout<<getK(k)<<endl;
	return 0;
}