UVaOJ 1591 - Data Mining

问题描述

解法一：阅读理解 + 等差数列

这题需要好好地理解题目描述，在工作中也会出现这种通过内存换计算效率的应用情景。

对于数组 $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 类型，一定能涵盖题目中给出的数据范围。

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ