找第ｋ小丑数：
用小顶堆每次取顶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;
}