[C_CH13-中] 坑洞路面

這題是 e-tutor 的題目，網址請點這兒。

分類上屬於中等。我個人認為這個題目的風格就像是大型比賽的風格了。乍看之下會沒有頭絮，要仔細思考後，才能發現解題的線索。

題目檢視

先看看題目，請配合下圖服用囉。

圖中土色的部分，代表「地表面」。

藍色的部分，代表「積水」。

最上面那排數字，代表那一格的「高度」。

最下面那排數字，代表「位置」。

所以合起來就是第 0 個位置，高度為 3， 0 積水。

第1個位置，高度為2，積水 1 格。

路面積水的示意圖

這題的輸出、以及輸出如下圖所示：

輸入以及輸出的範列

我們要輸出「總」積水量，以前述的範例來說，就是要輸出 1 + 2 + 2+ 1= 6。

觀察

第一件事，就是最「邊邊」永遠不會積水。以上圖來說，位置 0 以及位置 6 永遠不會積水。

為什麼？

因為位置 -1 以及位置 7 的高度為 0，水往低處流，所以最邊邊是不會積水的。

第二件事，不是「最邊邊」的位置，我要怎麼判斷會不會積水？

還是透過「大問題，拆小問題」的套路來解。

針對每個位置，我們要問兩個問題：

1. 針對位置 [i]，我怎麼知道它「會不會」積水？
2. 針對位置 [i]，如果它會積水，積水有多高？

如果位置 [i] 的問題可以解決，那就可以推而廣之，把整個問題解掉了。

先舉一個實例來看看吧！

位置 [2] 會積水嗎？

我們看位置 [2] 會不會積水。

一看就知道會積水。但電腦不會「看」呀，所以我們要教它判斷的邏輯。

位置 [2] 會積水，是因為它是個凹洞。 嗯，這個回答有點接近了，但電腦還不能處理。因為「凹洞」這個詞太模糊了。電腦通常處理的是「數字」，因此我們必需把凹洞這個意思，轉成可以計算的「數字」才可以。

再問下去，「凹洞」有什麼特質？

因為位置 [2] 的高度比 (1) 左邊的高度，以及 (2) 右邊的高度，來得 小！

Bingo！這就可以解了，因為高度是個數值，電腦可以運算！

所以我們只要從位置 [2] 這個地方開始，由左，由右掃描，只要發現有比它高的路面，那位置 [2] 就會積水。

以下圖為例，箭號所指之處，就是比位置 [2] 還要高的路面，所以位置 [2] 會積水。

位置 [2] 的高度為 1
位置 [2] 右邊比它高 (為 4)
位置 [2] 左邊比它高 (為 2)

位置 [2] 的積水有多高？

知道位置 [2] 會積水後，那就要分析積水會有多高了。

這時要多分析幾個例子，才能確保沒有錯。

首先看下圖，直覺上可能會想說，由位置 [2] 往右邊找到比它高的地點。再往位置 [2] 左邊找比它高的地點，就會得到下圖兩個箭號的點。

我們稱位置 [2] 右邊比較高的點為 rmax，所以 rmax = 4。

我們稱位置 [2] 左邊比較高的點為 lmax，所以 lmax = 3。

然後取這兩者的最小，稱為 min_max，所以 min_max = max(rmax, lmax)  = 3。

把 min_max 減去 [2] 的高度，就得到 min_max - 1 = 3 - 1 ==> 2。

於是 2 就是 [2] 的積水高度！

這種想法是錯的！

在位置 [2] 右邊，比 [2] 還要高的點為 rmax
在位置 [2] 左邊，比 [2] 還要高的點為 lmax

看下圖囉。

如果用前述的邏輯去解的話，會發算出來 [2] 的積水為 2。

但實際上我們發現 [2] 的積水為 4 才對。

所以問題出在，我們要找的 rmax 是 [2] 右邊「最高」的點，所以實際上 rmax 為 5。

我們要找的 lmax 是 [2] 左邊「最高」的點，所以 lmax = 5。

因此 min_max = min(rmax, lmax) = 5。

所以積水為 min_max - 1 ==> 4。

可以寫 code 了

分析到這兒，可以開始寫 code 了。

首先先把資料讀入，這部分很簡單，就不解說了，直接上程式碼。

	int n;
	cin >> n;
	int arr[1000] = { 0 };
	for (int i = 0; i < n; i++)
	{
	cin >> arr[i];
	}

view raw C_CH131.cpp hosted with ❤ by GitHub

底下是找到某個位置左邊最大值的程式碼。
pos 代表目前所在的位置。迴圈由 0 掃到 pos，就是找 pos 左邊的最高點，也就是 lmax 了。

以上圖來說， pos 就是 [2]，而迴圈就是找 [0], [1], [2]，看看 lmax 為何。

	//檢查左邊最大值
	int lmax = 0;
	for (int j = 0; j <= pos; j++)
	{
	if (arr[j] > lmax)
	{
	lmax = arr[j];
	}
	}

view raw C_CH132.cpp hosted with ❤ by GitHub

底下是找 rmax 的程式碼，由於邏輯和上面是一樣的，就不多說明了。

	int rmax = 0;
	for (int j = pos; j < n; j++)
	{
	if (arr[j] > rmax)
	{
	rmax = arr[j];
	}
	}

view raw C_CH133.cpp hosted with ❤ by GitHub

最後是找出 minmax，程式碼如下，這部分就更簡單了，單純由兩個數中找最小即可。

	int minmax = 0;
	if (rmax > lmax)
	minmax = lmax;
	else
	minmax = rmax;

view raw C_CH134.cpp hosted with ❤ by GitHub

最後就可以組出完整的程式囉。

	#include<iostream>
	using namespace std;
	int main()
	{
	int n;
	cin >> n;
	int arr[1000] = { 0 };
	for (int i = 0; i < n; i++)
	{
	cin >> arr[i];
	}
	int sum = 0;
	//因為邊界的地方不會積水，所以由 1 掃描到 n-2 即可。
	for (int pos = 1; pos < n - 1; pos++)
	{
	//檢查左邊最大值
	int lmax = 0;
	for (int j = 0; j <= pos; j++)
	{
	if (arr[j] > lmax)
	{
	lmax = arr[j];
	}
	}
	//檢查右邊最大值
	int rmax = 0;
	for (int j = pos; j < n; j++)
	{
	if (arr[j] > rmax)
	{
	rmax = arr[j];
	}
	}
	int minmax = 0;
	if (rmax > lmax)
	minmax = lmax;
	else
	minmax = rmax;
	//sum = sum + (minmax - arr[pos]);
	sum += minmax - arr[pos];
	}
	cout << sum << endl;
	return 0;
	}

view raw C_CH135.cpp hosted with ❤ by GitHub

更精緻的寫法

其實在陣列中找某個區間的最大值， C++ 有提供現成的 max_element 可以使用。所以我們不用自己寫。

前述程式碼中 17 行到 34 行可以簡化。

此外，求 min 也有現成的函式。所以整個程式碼可以更改如下。

	#include<iostream>
	#include<algorithm>
	using namespace std;
	int main()
	{
	int n;
	cin >> n;
	int arr[1000] = { 0 };
	for (int i = 0; i < n; i++)
	{
	cin >> arr[i];
	}
	int sum = 0;
	for (int pos = 1; pos < n - 1; pos++)
	{
	//檢查左邊最大值
	int lmax = *max_element(arr, arr + pos + 1);
	//檢查右邊最大值
	int rmax = *max_element(arr + pos, arr + n);
	int minmax = min(rmax, lmax);
	sum += minmax - arr[pos];
	}
	cout << sum << endl;
	return 0;
	}

view raw C_CH136.cpp hosted with ❤ by GitHub

這兒我們呼叫了 max_element 來找陣列中的最大值，所以記得引入 algorithm 這個標頭檔。可以看得出來，程式碼精簡許多。

比賽時，如果可以善用 C++ 本身提供的函式庫，是可以少打許多程式碼。而且 C++ 提供的函式已經通過很嚴格的測試，可以說不會有任何的錯誤，這比自己動手來說，少了很多的問題。建議可能的話，盡可能用標準函式庫中的程式了。