算法:多路归并
时间复杂度:$O(nlog(k))$
多路归并应该并不是那么直接就能够看出来。
实际则是要利用 $S = \left\{ p_1, p_2, a_3, …, p_k \right \}$ 进行构造丑数。
设丑数集合设为 $T = \left\{ a_1, a_2, a_3, …, a_t \right \}$。
$S_1 = \left\{T \times p_1\right\}$
$S_2 = \left\{T \times p_2\right\}$
$S_3 = \left\{T \times p_3\right\}$
$…$
$S_k = \left\{T \times p_k\right\}$
则利用 $k$ 路归并 得到丑数得集合:$T = \left\{1\right\} \cup S_1 \cup S_2 \cup … \cup S_k$。
而每个序列可用一个指针来走,注意实际在构造丑数时,仅利用了质因子 $S$ 集合,每个质因子也可使用多次,在遇到相同的 $a$ 时,判重即可,可利用小根堆进行优化。
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, k;
struct Data {
// v 代表当前的数值大小
// q 代表当前属于的序列
// k 对应于原S 中的下标
int v, p, k;
// 定义一个小根堆
bool operator< (const Data& t) const {
return v > t.v;
}
};
int main()
{
cin >> k >> n;
vector<int> q(1, 1);
++n;
priority_queue <Data> heap;
while (k--) {
int p;
cin >> p;
heap.push({p, p, 0});
}
while (q.size() < n) {
auto t = heap.top();
heap.pop();
q.push_back(t.v);
heap.push({t.p * q[t.k + 1], t.p, t.k + 1});
while (heap.top().v == t.v) {
auto r = heap.top();
heap.pop();
heap.push({r.p * q[r.k + 1], r.p, r.k + 1});
}
}
cout << q.back() << endl;
return 0;
}
// q 代表当前属于的序列
注释好强错了// q 代表当前属于的序列
结构体里的注释写错了吧?应该是 $p$ 吧