刘汝佳《算法竞赛入门经典（第二版）》第四章习题（4-9~4-10）
习题4-9 数据挖掘（Data Mining，ACM/ICPC NEERC 2003，UVa1591）
有两个n元素数组P和Q。P数组每个元素占SP个字节，Q数组每个元素占SQ个字节。有时需直接根据P数组中某个元素P(i)的偏移量Pofs(i)算出对应的Q(i)的偏移量Qofs(i)。当两个数组的元素均为连续存储时Qofs(i) = Pofs(i)/SP*SQ，但因为除法慢，可以把式子改写成速度较快的Qofs'(i)=(Pofs(i)+Pofs(i)<<A)>>B。为了让这个式子成立，在P数组仍然连续存储的前提下，Q数组可以不连续存储（但不同数组元素的存储空间不能重叠）。这样做虽然会浪费一些空间，但是提升了速度，是一种用空间换时间的方法。
输入n、SP和SQ（N≤220，1≤SP，SQ≤210），你的任务是找到最优的A和B，使得占的空间K尽量小。输出K、A、B的值。多解时让A尽量小，如果仍多解则让B尽量小。
原题描述
Dr. Tuple is working on the new data-mining application for Advanced Commercial Merchandise Inc.One of the subroutines for this application works with two arraysPandQcontainingNrecords of dataeach (records are numbered from 0 toN−1). ArrayPcontains hash-like structure with keys. ArrayPis used to locate record for processing and the data for the corresponding record is later retrievedfrom the arrayQ.
All records in arrayPhave a size ofSPbytes and records in arrayQhave size ofSQbytes. Dr.Tuple needs to implement this subroutine with the highest possible performance because it is a hot-spotof the whole data-mining application. However,SPandSQare only known at run-time of applicationwhich complicates or makes impossible to make certain well-known compile-time optimizations.
The straightforward way to find byte-offset ofi-th record in arrayPis to use the following formula:
Pofs(i) =SP·i,(1)
and the following formula for arrayQ:
Qofs(i) =SQ·i.(2)
However, multiplication computes much slower than addition or subtraction in modern processors.Dr. Tuple avoids usage of multiplication while scanning arrayPby keeping computed byte-offsetPofs(i) ofi-th record instead of its indexiin all other data-structures of data-mining application. Heuses the following simple formulae when he needs to compute byte-offset of the record that precedes orfollowsi-th record in arrayP:
Pofs(i+ 1) = Pofs(i) +SP
Pofs(i−1) = Pofs(i)−SP
Whenever a record from arrayPis located by either scanning of the array or by taking Pofs(i) fromother data structures, Dr. Tuple needs to retrieve information from the corresponding record in arrayQ. To access record in arrayQits byte-offset Qofs(i) needs to be computed. One can immediatelyderive formula to compute Qofs(i) with known Pofs(i) from formulae (1) and (2):
Qofs(i) = Pofs(i)/SP·SQ(3)
Unfortunately, this formula not only contains multiplication, but also contains division. Even thoughonly integer division is required here, it is still an order of magnitude slower than multiplication onmodern processors. If coded this way, its computation is going to consume the most of CPU time indata-mining application for ACM Inc.
After some research Dr. Tuple has discovered that he can replace formula (3) with the followingfast formula:
Qofs’(i) = (Pofs(i) + Pofs(i)<< A)>> B(4)
where AandBare non-negative integer numbers, “<< A” is left shift byAbits (equivalent to integermultiplication by 2A), “>> B” is right shift byBbits (equivalent to integer division by 2B).
This formula is an order of magnitude faster than (3) to compute, but it generally cannot alwaysproduce the same result as (3) regardless of the choice for values ofAandB. It still can be used if oneis willing to sacrifice some extra memory.
Conventional layout of arrayQin memory (using formula (2)) requiresN·SQbytes to store theentire array. Dr. Tuple has found that one can always choose suchKthat if he allocatesKbytes ofmemory for the arrayQ(whereK≤N·SQ) and carefully selects values forAandB, the fast formula(4) will give non-overlapping storage locations for each of theNrecords of arrayQ.
Your task is to write a program that finds minimal possible amount of memoryKthat needs tobe allocated for arrayQwhen formula (4) is used. Corresponding values forAandBare also to befound. If multiple pairs of values forAandBgive the same minimal amount of memoryK, then thepair whereAis minimal have to be found, and if there is still several possibilities, the one whereBis minimal. You shall assume that integer registers that will be used to compute formula (4) are wideenough so that overflow will never occur.
Input
Input consists of several datasets. Each dataset consists of three integer numbersN,SP, andSQseparatedbyspaces(1≤N≤220,1≤SP≤210,1≤SQ≤210).
Output
For each dataset, write to the output file a single line with three integer numbersK,A, andB separatedby spaces.
题解
题目理解起来并不难，关键是K的初始值的设置和A、B值的上限问题。首先，即使Q连续存储，也要占用n*y字节，那么偏移量最小也是n*y*2^10。其次，数据规模为230，那么A和B作为幂，其值肯定不会超过32。另外最优解出现多解时依次考虑A、B，那么只需要将A设置在外循环，B在内循环即可。这几点明确了，只需要套公式计算K值，更新最优解就行了。
源代码
#include <iostream>
int main (void)
{
using std::cin;
using std::cout;
long long n, sp, sq;
while (cin >> n >> sp >> sq)
{
long long a, b, K = n*sq<<10, A = 0, B = 0;//K的初始值很关键下面的循环终止条件要用到
for (a = 0; a < 32; a++)
for (b = 0; b < 32; b++)
{
long long temp = (((n-1)*sp+((n-1)*sp<<a))>>b)+sq;
if (temp >= n*sq && temp < K)
K = temp, A = a, B = b;
}
cout << K << " " << A << " " << B << std::endl;
}
return 0;
}
运行结果
习题4-10 洪水！（Flooded! ACM/ICPC World Finals 1999, UVa815）
有一个n*m（1≤m，n<30）的网格，每个格子是边长10米的正方形，网格四周是无限大的墙壁。输入每个格子的海拔高度，以及网格内雨水的总面积，输出水位的海拔高度以及有多少百分比的区域有水（即高度严格小于水平面）。
原题描述
To enable homebuyers to estimate the cost of flood insurance, a real-estate firm provides clients withthe elevation of each 10-meter by 10-meter square of land in regions where homes may be purchased.Water from rain, melting snow, and burst water mains will collect first in those squares with thelowest elevations, since water from squares of higher elevation will run downhill. For simplicity, we alsoassume that storm sewers enable water from high-elevation squares in valleys (completely enclosed bystill higher elevation squares) to drain to lower elevation squares, and that water will not be absorbedby the land.
From weather data archives, we know the typical volume of water that collects in a region. Asprospective homebuyers, we wish to know the elevation of the water after it has collected in low-lying squares, and also the percentage of the region’s area that is completely submerged (that is, thepercentage of 10-meter squares whose elevation is strictly less than the water level). You are to writethe program that provides these results.
Input
The input consists of a sequence of region descriptions. Each begins with a pair of integers,mandn, each less than 30, giving the dimensions of the rectangular region in 10-meter units. Immediatelyfollowing aremlines ofnintegers giving the elevations of the squares in row-major order. Elevationsare given in meters, with positive and negative numbers representing elevations above and below sealevel, respectively. The final value in each region description is an integer that indicates the number ofcubic meters of water that will collect in the region. A pair of zeroes follows the description of the lastregion.
Output
For each region, display the region number (1, 2, ...), the water level (in meters above or below sealevel) and the percentage of the region’s area under water, each on a separate line. The water leveland percentage of the region’s area under water are to be displayed accurate to two fractional digits.Follow the output for each region with a blank line.
题解
将格子按海拔高度从低到高排列，依次向里面“注水”，直到平均水位低于海平面为止。源代码
#include <iostream>
#include <algorithm>
#include <iomanip>
int main (void)
{
using std::cin;
using std::cout;
int n, m, num = 0;
while (cin >> m >> n && m && n)
{
int i, j;
double water;
num++;
int *p = new int[m*n];
for (i = 0; i < m*n; i++)
cin >> p[i];
std::sort(p, p+m*n);
cin >> water;
water /= 100.0;
for (j = 1; j <= m*n; j++)
{
water += p[j-1];
if (water/j <= p[j])
break;
}
cout << "Region " << num << std::endl;
cout << "Water level is " << std::fixed << std::setprecision(2) << water/j << " meters.\n";
cout << std::fixed << std::setprecision(2) << j*100.0/(m*n) << " percent of the region is under water.\n\n";
delete []p;
}
return 0;
}
运行结果
