考点
题解
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 50;
const ll inf = 1e18;
int n, k, alen, blen, in[20];
ll a[maxn], b[maxn];
void dfs1(int idx, ll sum) {
if (idx > n) {
a[++alen] = sum;
return;
}
for (ll now = 1;; now *= in[idx]) {
if (inf / now < sum) break;
dfs1(idx + 2, sum * now);
}
}
void dfs2(int idx, ll sum) {
if (idx > n) {
b[++blen] = sum;
return;
}
for (ll now = 1;; now *= in[idx]) {
if (inf / now < sum) break;
dfs2(idx + 2, sum * now);
}
}
bool check(ll mid) {
int cnt = 0;
for (int i = 1, j = blen; i <= alen; ++i) {
while (j >= 1 && mid / a[i] < b[j]) --j;
cnt += j;
}
return cnt < k;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> in[i];
cin >> k;
dfs1(1, 1), dfs2(2, 1);
sort(a + 1, a + 1 + alen), alen = unique(a + 1, a + 1 + alen) - 1 - a;
sort(b + 1, b + 1 + blen), blen = unique(b + 1, b + 1 + blen) - 1 - b;
ll l = 0, r = 1e18;
while (l <= r) {
ll mid = (l + r) / 2;
if (check(mid))
l = mid + 1;
else
r = mid - 1;
}
cout << l << endl;
return 0;
}
|
思路
由于暴力枚举的数字大小顺序是完全打乱的，你不可能即时知道当前的枚举结果到底在整体结果当中排第几。
所以只能考虑二分答案，去直接找哪个数字有k个小于等于它的。
使用双向DFS进行枚举。
以前常用的是以长度对半分，比如一共16个数，先枚举前8个数的情况，再枚举后8个数的情况，最后组合合并。
在本题中，同样也是拆分成两个最多有8个质因子的子集合，子集合内枚举不超过1e18的数字，最后两个子集合的枚举情况合并。
但是这里不能使用长度对半分，而要按照下标奇偶性均分，否则会超时！
这是因为题目所给的输入已经是有序且不重的，那么前8个数一定小于后8个数，前8个数的枚举情况显然远大于后8个数，
为了平衡时间复杂度，按照下标奇偶性均分即可。
得到了奇数位置的枚举情况a，长度为alen；偶数位置的枚举情况b，长度为blen；且两个数组都是有序且去重的。
要判断有多少个数小于等于mid，直接用双指针思想：
a的游标i从1出发，为外层循环；b的游标j从blen出发，为内层循环；a[i] * b[j]大于mid，就--j
直到第一个乘积小于等于mid，此时j就等于a[i]所有情况中，小于等于mid的情况个数。
可以使用双指针，是因为j不可能回头，因为a[i + 1]一定大于a[i]，那么a[i + 1] * b[j] > a[i] * b[j]，
你要找小于等于mid的情况，为什么还要往大的方向回头找呢？