【Day 19】Algorithm - Practice 1

题目

xLimit = n;
yLimit = m;
population = pij：坐落在(i, j)的人口数;
distance = r：医院覆盖距离;
(u, v)：给定的医院座标

第一种演算法

建立一个存各城镇人口数的阵列：populationArray[xLimit][yLimit] = {0}
coverPopulation = 0    // 盖这间医院所覆盖到的人口数

// 扫过所有在xLimit X yLimit中的点
for i in range (0 ~ xLimit)
    for j in range (0 ~ yLimit)
        if abs(u - i) + abs(v - j) <= distance
			coverPopulation += populationArray[i][j]

Time complexity
O(1 + xLimit * yLimit) = O(xLimit * yLimit)

第二种演算法

这个方法是将举行切成四等份：

// 矩形左上角
for i in range (从u - 1开始往左减, 在|i – u| <= distance内 && i >= 0)
	for j in range (从v开始, 在|j - v| <= distance内 && |i - u| + |j - v| <= distance内 && j <= yLimit)
		coverPopulation += populationArray[i][j]
// 矩形右上角
for i in range (从u开始往右加, 在|i – u| <= distance内 && i <= xLimit)
	for j in range (从v开始往上加, 在|j - v| <= distance内 && j <= yLimit)
		coverPopulation += populationArray[i][j]
// 矩形左下角
for i in range (从u - 1开始往左减, 在|i – u| <= distance内 && i >= 0)
	for j in range (从v – 1开始往下减, 在|j - v| <= distance内 && j >= 0)
		coverPopulation += populationArray[i][j]
// 矩形右下角
for i in range (从u开始往右加, 在|i – u| <= distance内 && i <= xLimit)
	for j in range (从v - 1开始往下减, 在|j - v| <= distance内 && j >= 0)
		coverPopulation += populationArray[i][j]

Time complexity
最多跑distance * distance次，所以 big O 为 O(distance^2)

在第一种演算法中，需要计算地图上每一个点是否在给定医院座标的范围内，因此必须计算xLimit * yLimit次。
而在第二种演算法中，由於 for 回圈已经限制要讨论的座标范围，因此最多只需讨论distance * distance次就能计算出所覆盖的人口数。
xLimit * yLimit >= distance * distance，所以第二种演算法更有效率。

而这样的核心架构可以衍生出第二题：找出能造福最多民众的医院院址，计算其覆盖的民众总人数，并将之输出。

输入输出格式：

其实这题并不难，按照上述第二种演算法即可（第一种演算法可能会面临 time limit exceed 的问题)，不过这题 tricky 的地方在於他输入的部分，第 2 行至第 m + 2 行所输入的资料为每行固定 y 座标，因此当我们把输入的座标 (i, j) 城镇的人口数存进阵列(populationArray)时，不能用我最熟悉的 i 代表 x 座标、y 代表 y 座标：

而是要将 i, j 所表示的反过来：

我在写的时候因为这个输入格式没看清楚卡了超久..题目真的要看清楚ㄚ！