【Day 20】Algorithm - Practice 2

接下来是一题迄今为止，作业中最复杂的一题，虽然不会太难，但是要把逻辑整理清楚，而且给予自己足够的信心！

题目

演算法

Sol.
本题我们要宣告两个函数：
1.marginalBenefit：我们以这个函数来计算盖这座铁路的效益
2.railwayBuilding：若要新盖铁路则回传新铁路所带来的效益
而由於railBuilding中计算边际效益比率时有可能会计算出小数，因此须将两函数都的型态都设为float。

在 main function 中，我们要建四个阵列：
1.populationArray：存各村庄村民数
2.stationLocation：存车站座标
{[x1,y1], [x2,y2], [x3,y3], [x4,y4],……}
3.stationArray：标记有无车站或铁路
(无车站或铁路：0, 有车站无铁路：1, 有铁路：2)

利用以上已知的资讯找寻其是否有可能可以建造的铁路路段，并存进第四个阵列potentialRailway。

4.potentialRailway：可能可以建造的铁路
{[x起始车站, y起始车站, x终点车站, y终点车站, 铁路长度, 是否已建(未建：0, 建：1), 车站编号合计, 车站编号较小值], ……}

Pseudocode

float marginalBenefit：
	这段铁路的受益人数b = 0.0
	// 垂直方向铁路：
	if这段铁路没盖过 (在stationArray中 != 2)
		b += 此村庄村民数
	// 水平方向铁路：
	if 这段铁路没盖过 (在stationArray中 != 2)
		b += 此村庄村民数
	
	return b;

float railwayBuilding：
	候选铁路路段railway = 0;
	边际效益b = 0.0;
    最大边际效益比率maxRatio = 0.0;
    最大边际效益maxb = 0.0;
    for (i = 0 ~ 可建造铁路总数)
        if (预算够 && 此铁路还未建造)
            呼叫函数marginalBenefit
            if (这条铁路的边际效益比率 > maxRatio)
                更新maxRatio, maxb, railway
            if (这条铁路的边际效益比率 == maxRatio)
                选长度短的
                else if 长度一样
                    选编号合计小的
                    else if 编号合计一样
                        选两条铁路间较小车站编号最小的
    if (maxb > 0)
        将potentialRailway[railway][5]改成1
        并将stationArray中车站会经过的点都改成2
    else
        maxb = 0;

    return maxb;

main function：

建populationArray、stationLocation、stationArray、potentialRailway
// 垂直方向铁路：
宣告一布林值flag = false，
for (int i = 0; i <= xLimit; i++)
    flag = false;
	for (int j = 0; j <= yLimit; j++) 
		找起始车站 (若找到则将false改为true)
		若找到终点车站则将此铁路的资料存进potentialArray
		并将终点车站更新为起始车站，并继续找    // 注1

// 水平方向铁路：	(方法与找垂直方向铁路相同)
for (int i = 0; i <= yLimit; i++)
    flag = false;
    for (int j = 0; j <= xLimit; j++)
        找起始车站 (若找到则将false改为true)
        若找到终点车站则将此铁路的资料存进potentialArray
        并将终点车站更新为起始车站，并继续找    // 注1


执行函数 railwayBuilding
可造福的村民数coverPeople += maxb;
While (maxb != 0)
	判断budget是否还足够
	执行函数 railwayBuilding
	coverPeople += maxb;
	if (maxb == 0)
		break

输出 coverPeople 及剩余预算 budget

注1：一定要将目前找到的第二个车站更新为第一个车站来找，不然接下来的判断就会直接跳过第二个车站而可能造成少判断一段铁路。