接下來是一題迄今為止，作業中最複雜的一題，雖然不會太難，但是要把邏輯整理清楚，而且給予自己足夠的信心！

題目

演算法

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：一定要將目前找到的第二個車站更新為第一個車站來找，不然接下來的判斷就會直接跳過第二個車站而可能造成少判斷一段鐵路。