UVa 1591 Data Mining

题目分析

问题背景

Dr. Tuple\texttt{Dr. Tuple}Dr. Tuple正在为ACM\texttt{ACM}ACM公司开发一个数据挖掘应用程序，其中包含两个数组PPP和QQQ，每个数组都有NNN条记录。数组PPP中的记录大小为SPS_PSP​字节，数组QQQ中的记录大小为SQS_QSQ​字节。

核心问题

在访问数组QQQ时，需要计算记录的字节偏移量。直接的计算公式为：
Qofs(i)=Pofs(i)SP×SQQofs(i) = \frac{Pofs(i)}{S_P} \times S_QQofs(i)=SP​Pofs(i)​×SQ​
这个公式包含乘法和除法运算，在现代处理器上效率较低。

优化方案

Dr. Tuple\texttt{Dr. Tuple}Dr. Tuple提出了一个快速计算公式：
Qofs′(i)=(Pofs(i)+(Pofs(i)≪A))≫BQofs'(i) = (Pofs(i) + (Pofs(i) \ll A)) \gg BQofs′(i)=(Pofs(i)+(Pofs(i)≪A))≫B
其中：

• ≪A\ll A≪A表示左移AAA位（相当于乘以2A2^A2A）
• ≫B\gg B≫B表示右移BBB位（相当于除以2B2^B2B）

这个公式等价于：
Qofs′(i)=⌊Pofs(i)×(1+2A)2B⌋Qofs'(i) = \left\lfloor \frac{Pofs(i) \times (1 + 2^A)}{2^B} \right\rfloorQofs′(i)=⌊2BPofs(i)×(1+2A)​⌋

任务目标

我们需要找到最优的AAA和BBB，使得：

1. 所有记录的Qofs′(i)Qofs'(i)Qofs′(i)互不重叠
2. 所需内存KKK最小
3. 如果多个(A,B)(A,B)(A,B)得到相同的KKK，选择AAA最小的，再选择BBB最小的

关键约束

为了保证记录不重叠，需要满足：
SP×(1+2A)2B≥SQ\frac{S_P \times (1 + 2^A)}{2^B} \ge S_Q2BSP​×(1+2A)​≥SQ​

所需内存的计算公式为：
K=⌊(N−1)×SP×(1+2A)2B⌋+SQK = \left\lfloor \frac{(N-1) \times S_P \times (1 + 2^A)}{2^B} \right\rfloor + S_QK=⌊2B(N−1)×SP​×(1+2A)​⌋+SQ​

算法思路

1. 枚举所有可能的AAA和BBB（范围设为000到313131）
2. 检查是否满足约束条件SP×(1+2A)≥SQ×2BS_P \times (1 + 2^A) \ge S_Q \times 2^BSP​×(1+2A)≥SQ​×2B
3. 如果满足条件，计算对应的KKK值
4. 选择最小的KKK，如果KKK相同则按题目要求选择AAA和BBB

代码实现

// Data Mining// UVa ID: 1591// Verdict: Accepted// Submission Date: 2025-10-20// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<iostream>#include<climits>usingnamespacestd;intmain(){longlongN,SP,SQ;while(cin>>N>>SP>>SQ){longlongbestK=LLONG_MAX;// 初始化最佳K为最大值intbestA=-1,bestB=-1;// 初始化最佳A和B// 枚举所有可能的A和Bfor(intA=0;A<=31;A++){for(intB=0;B<=31;B++){// 检查是否满足不重叠条件if(SP*(1LL+(1LL<<A))>=SQ*(1LL<<B)){// 计算所需内存KlonglongK=((N-1)*SP*(1LL+(1LL<<A)))/(1LL<<B)+SQ;// 更新最优解if(K<bestK){bestK=K;bestA=A;bestB=B;}elseif(K==bestK){// K相同时，选择A较小的if(A<bestA){bestA=A;bestB=B;}elseif(A==bestA&&B<bestB){// A相同时，选择B较小的bestB=B;}}}}}// 输出结果cout<<bestK<<" "<<bestA<<" "<<bestB<<endl;}return0;}

复杂度分析

• 时间复杂度：O(32×32)=O(1024)O(32 \times 32) = O(1024)O(32×32)=O(1024)，对于每个测试数据都是常数时间
• 空间复杂度：O(1)O(1)O(1)，只使用了几个变量

该算法通过枚举所有可能的(A,B)(A,B)(A,B)组合，确保找到满足条件的最优解，同时保证了高效性。