MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1591 - Data Mining
AOAPC II

UVaOJ 1591 - Data Mining

Chai
2021-11-24 0:00:00在线评测阅读 388

问题描述

p1591

原题链接:UVaOJ 1591 - Data Mining

相关说明:本题为《算法竞赛入门经典(第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 类型,一定能涵盖题目中给出的数据范围。

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz