问题描述
p1591相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-9
解法一：阅读理解 + 等差数列
这题需要好好地理解题目描述，在工作中也会出现这种通过内存换计算效率的应用情景。
对于数组 $P$ 和 $Q$ 都是内存连续存储的情况，已知 $P$ 数组每个元素占据 $S_P$ 个字节，$Q$ 数组每个元素占据 $S_Q$ 个字节，那么可以根据 $P$ 数组中某个元素 $P(i)$ 的偏移量 $P_{ofs}(i)$ 算出对应的 $Q(i)$ 的偏移量 $Q_{ofs}(i)$, 连续存储的情况下计算公式为 $Q_{ofs}(i)=P_{ofs}(i)/S_P \cdot S_Q$. （假定 $P_{ofs}(1)=0$ ）。但是对于 CPU 来说，这样的计算比较慢。因此题目作者给出了另一种映射形式 $Q_{ofs}(i)=(P_{ofs}(i)+P_{ofs}(i)<<A)>>B$, 用移位运算来完成 $P_{ofs}(i) \mapsto Q_{ofs}(i)$ 的一一映射。
问题在于，想要使得上面的映射形式成立， $Q$ 数组的每个元素在内存中将不再是连续相邻分布的，会变成散列（或者说这已经变成了哈希的情况）。且相较于原来的 $N \cdot S_Q$ 字节将会占据更多的内存空间，记为 $K$ 字节，对应有 $K \geq N \times S_Q$ 一定成立 （原题中给出的范围有误！）。注意不是任何的 $K$ 大小的内存都能存在对应的 $A$ 和 $B$ 代入公式。我们首先需要保证 $Q$ 数组中的元素在内存中地址没有重叠，在这道题中就意味着对任意 $i$. 有 $Q_{ofs}(i)-Q_{ofs}(i-1) \geq S_Q$ 需要恒成立。
好在式子 $Q_{ofs}(i)$ 其实是一个 $d$ 等差数列，可求得：
$$
\begin{align}Q_{ofs}(i)-Q_{ofs}(i-1)
&=(P_{ofs}(i)+P_{ofs}(i)<<A)>>B - (P_{ofs}(i-1)+P_{ofs}(i-1)<<A)>>B \\
&=(P_{ofs}(i)-P_{ofs}(i-1)) \cdot (1 + 1<<A)>>B \\
&= S_P \cdot (1 + 1<<A)>>B \\
&= (S_P +S_P << A) >> B \quad == d \geq S_Q
\end{align}$$
化简可得对此时的 $A$ 和 $B$ 有 $S_P + (S_P << A) \geq (S_Q << B)$. 注意位运算优先级。
对于给定的 $A$ 和 $B$, 数组 $Q$ 中的最后一个元素的偏移量为 $Q_{ofs}(n) = (S_P \cdot (n-1) + S_P \cdot (n-1) << i)>>j$, 那么至少需要的内存字节数为 $k = Q_{ofs}(n) + S_Q$. 因此此题的解法就可以是暴力枚举所有的 $A$ 和 $B$, 找出满足要求的最小的 $K$ 值（此时维护的 $A$ 和 $B$ 也是最小情况，见代码逻辑）。由于移位运算可能会溢出，所以数据类型使用了 long long 类型，一定能涵盖题目中给出的数据范围。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <bits/stdc++.h> using namespace std; int main() { long long n, sp, sq; while (cin >> n >> sp >> sq) { long long k = LONG_LONG_MAX, a, b; for (int i = 0; i < 32; ++i) // a for (int j = 0; j < 32; ++j) // b if ((sp + (sp << i)) >= (sq << j)) { // Qofs(n) - Qofs(n-1) >= sq long long cur_k = ((sp * (n - 1) + ((sp * (n - 1)) << i)) >> j) + sq; if (cur_k < k) k = cur_k, a = i, b = j; } cout << k << " " << a << " " << b << endl; } return 0; } |
|
1 |
#TODO |
