时间复杂度的计算是个技术活
丑数
第一次想到的是用一个小根堆，每次取出最小值，乘其它数的积插入堆中，最后取出的第 $n$ 个就是答案，然鹅，时间（ $O(n^2\log n)$ ）和空间（ $O(n^2)$ ）上都不允许（ $n \le 10^5$ 太艹了）
然后发现其实真正有用的跟新只有 $f[i] * a[i]$ 的形式，其中 $f[i]$ 表示第 $i$ 个丑数， $a[i]$ 表示质数，由于 $k$ 很小，用平衡树维护貌似可做？（黄题啊，平衡树个寂寞啊）
最后实在 不想打平衡树 想不出来，一看题解：艹，暴力求第 $n$ 个就好了，加个记录的优化，时间复杂度 $O(nk \xi)$ ，其中 $\xi$ 代表玄学因子（因为没人知道那层while会跑多少），空间复杂度 $O(n)$
无语，这个故事告诉我们不要一看见 $10^5$ 就想 $n\log n$
似乎要long long
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5, K = 100 + 5;
const LL INF = (LL)1e18 + 7;
int k, n;
LL f[N];
int a[N], b[N];
int main()
{
scanf("%d%d", &k, &n);
for (int i = 1; i <= k; ++i)
scanf("%d", &a[i]);
sort(a + 1, a + 1 + k);
f[0] = 1;
LL mn;
for (int i = 1; i <= n; ++i)
{
mn = INF;
for (int j = 1; j <= k; ++j)
{
while (f[b[j]] * a[j] <= f[i - 1])
++b[j];
mn = min(f[b[j]] * a[j], mn);
}
f[i] = mn;
}
printf("%lld", f[n]);
return 0;
}
|