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)×(12A)2B⌋Qofs(i) \left\lfloor \frac{Pofs(i) \times (1 2^A)}{2^B} \right\rfloorQofs′(i)⌊2BPofs(i)×(12A)​⌋任务目标我们需要找到最优的AAA和BBB使得所有记录的Qofs′(i)Qofs(i)Qofs′(i)互不重叠所需内存KKK最小如果多个(A,B)(A,B)(A,B)得到相同的KKK选择AAA最小的再选择BBB最小的关键约束为了保证记录不重叠需要满足SP×(12A)2B≥SQ\frac{S_P \times (1 2^A)}{2^B} \ge S_Q2BSP​×(12A)​≥SQ​所需内存的计算公式为K⌊(N−1)×SP×(12A)2B⌋SQK \left\lfloor \frac{(N-1) \times S_P \times (1 2^A)}{2^B} \right\rfloor S_QK⌊2B(N−1)×SP​×(12A)​⌋SQ​算法思路枚举所有可能的AAA和BBB范围设为000到313131检查是否满足约束条件SP×(12A)≥SQ×2BS_P \times (1 2^A) \ge S_Q \times 2^BSP​×(12A)≥SQ​×2B如果满足条件计算对应的KKK值选择最小的KKK如果KKK相同则按题目要求选择AAA和BBB代码实现// Data Mining// UVa ID: 1591// Verdict: Accepted// Submission Date: 2025-10-20// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includeiostream#includeclimitsusingnamespacestd;intmain(){longlongN,SP,SQ;while(cinNSPSQ){longlongbestKLLONG_MAX;// 初始化最佳K为最大值intbestA-1,bestB-1;// 初始化最佳A和B// 枚举所有可能的A和Bfor(intA0;A31;A){for(intB0;B31;B){// 检查是否满足不重叠条件if(SP*(1LL(1LLA))SQ*(1LLB)){// 计算所需内存KlonglongK((N-1)*SP*(1LL(1LLA)))/(1LLB)SQ;// 更新最优解if(KbestK){bestKK;bestAA;bestBB;}elseif(KbestK){// K相同时选择A较小的if(AbestA){bestAA;bestBB;}elseif(AbestABbestB){// A相同时选择B较小的bestBB;}}}}}// 输出结果coutbestK bestA bestBendl;}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)组合确保找到满足条件的最优解同时保证了高效性。