15｜指標基本功

還沒完成C 或 C++ 皆可CPU 時間上限 1 秒

題目說明

C 或 C++ 皆可｜CPU 時間上限 1 秒｜這一題不計算記憶體，但檢查的第一階段會用 AddressSanitizer 抓指標越界

題目

讀入 n 個整數，依序做下面四件事：

找出最小值和最大值。最小值如果出現好幾次，取第一次出現的位置；最大值如果出現好幾次，取最後一次出現的位置。
計算所有整數的總和。
把「第一個最小值」和「最後一個最大值」這兩個元素交換，輸出交換後的陣列。
把（交換後的）整個陣列前後反轉，輸出反轉後的陣列。

這一題的重點不是演算法，而是用指標來做。你的程式必須寫出下面這些函式，並且真的用它們完成上面的工作：

函式	功能
`void swap_int(int a, int b)`	交換 `a` 和 `b` 的值
`void min_max(const int arr, int n, int out_min, int *out_max)`	把最小值、最大值分別寫到 `out_min`、`out_max`（一個函式「回傳」兩個值）
`int find_first(int begin, int *end, int value)`	從 `begin` 往後找，回傳第一個等於 `value` 的元素的指標
`int find_last(int begin, int *end, int value)`	從 `end` 往前找，回傳最後一個等於 `value` 的元素的指標
`long long sum_range(const int begin, const int end)`	用指標走過整段，回傳總和
`void reverse_range(int begin, int end)`	用兩個指標從兩端往中間走，搭配 `swap_int` 反轉
`void print_range(const int begin, const int end)`	輸出整段的元素，用一個空白分隔，最後換行

begin、end 表示一段範圍：begin 指向第一個元素，end 指向最後一個元素的下一個位置（只能拿來比較，不能用 *end 取值）。整個陣列就是 arr 到 arr + n。

規定：

find_first、find_last、sum_range、reverse_range、print_range 裡面不要用 arr[i] 這種索引寫法，要用指標移動（p++、p--）和取值（*p）。
位置（索引）用指標相減算出來：如果 p 指向陣列裡的某個元素，p - arr 就是它的索引。
用 C++ 的人也一樣用指標寫，這一題就是要練指標。（平常寫 C++ 時，swap_int 這類函式通常會改用參考 int &a，見下方複習重點。）

檢查程式沒辦法看出你有沒有照規定寫，請自己遵守，這樣練習才有意義。

輸入

第一行是一個整數 n（1 ≤ n ≤ 100000）。
第二行有 n 個整數 a₀, a₁, …, aₙ₋₁，以一個空白分隔，每個都在 −1000000000 到 1000000000 之間。

輸出

共 5 行：

min V at I：V 是最小值，I 是它第一次出現的索引（從 0 開始算）
max V at I：V 是最大值，I 是它最後一次出現的索引
sum S：S 是所有整數的總和（可能超過 int 的範圍）
交換第一個最小值和最後一個最大值之後的陣列，以一個空白分隔
把第 4 行的陣列反轉之後的結果，以一個空白分隔

n = 1 時最小值和最大值是同一個元素，「交換」它和自己，陣列不變。

範例

輸入：

8
3 -1 4 1 -1 9 2 9

輸出：

min -1 at 1
max 9 at 7
sum 26
3 9 4 1 -1 9 2 -1
-1 2 9 -1 1 4 9 3

說明：最小值 −1 出現在索引 1 和 4，取第一次的 1；最大值 9 出現在索引 5 和 7，取最後一次的 7。交換索引 1 和 7 的元素，得到第 4 行；再整個反轉得到第 5 行。

複習重點

共通（C 和 C++ 都一樣）：

&x 取得變數的位址，int *p = &x; 讓 p 指向 x，*p 就是 x 本身（可以讀也可以寫）
函式參數是「複製一份」傳進去的；想讓函式改到呼叫端的變數，就把變數的位址傳進去：swap_int(&a, &b)
用指標參數讓函式「回傳」好幾個值：min_max(arr, n, &mn, &mx)
陣列名稱在大部分情況會自動變成指向第一個元素的指標；arr[i] 和 *(arr + i) 完全相同
指標加減整數是「移動幾個元素」，不是幾個 byte；兩個指向同一個陣列的指標相減，得到它們之間差幾個元素
const int *p：不能透過 p 修改它指向的值，用來表示「這個函式只讀不改」
指標只能在陣列範圍內（加上 end 這個「最後一個的下一個」）移動，超出範圍就是未定義行為

C：

大陣列不要放在函式的區域變數（stack 只有大約 1 MB），可以用 static int arr[100000]; 或全域變數

C++：

可以用 std::vector<int> v(n); 存資料，再用 v.data() 拿到指向第一個元素的指標（vector 的元素在記憶體裡是連續的）
C++ 平常更常用參考（reference）：void swap_int(int &a, int &b)，呼叫時寫 swap_int(x, y)，不用 & 也不用 *。標準函式庫也有現成的 std::swap、std::minmax_element、std::reverse
參考一定要綁定一個變數、不能是空的、也不能改綁別的變數；需要「可能沒有」或「會移動」的時候才用指標

提示 1：swap_int 和 min_max 怎麼寫、怎麼呼叫？

void swap_int(int *a, int *b) {
    int tmp = *a;   // *a 是「a 指向的那個整數」
    *a = *b;
    *b = tmp;
}

// 呼叫端：
int mn, mx;
min_max(arr, n, &mn, &mx);   // 把 mn、mx 的位址傳進去，函式把答案寫到那裡

min_max 裡面先讓 *out_min = arr[0]; *out_max = arr[0];，再用迴圈比較其他元素。

提示 2：怎麼用指標走過一段範圍？

往後走（find_first、sum_range、print_range）：

for (const int *p = begin; p != end; p++) {
    // *p 是目前的元素
}

往前走（find_last）時要小心：end 不能取值，而且指標不能移到 begin 前面（連算出來都不行）。所以先比較、再減：

int *p = end;
while (p != begin) {
    p--;
    // 現在 *p 可以取值
}

找到的元素在原陣列的索引是 p - arr。

提示 3：reverse_range 的兩個指標

讓 lo 指向第一個、hi 指向最後一個（end - 1，因為 n ≥ 1 所以一定存在），每次交換 *lo 和 *hi，然後 lo 往後一格、hi 往前一格，直到兩個碰在一起（lo < hi 不成立）為止。

如果寫錯讓指標跑出陣列，按 Ctrl+Shift+B 檢查時，第一階段的 AddressSanitizer 會顯示 global-buffer-overflow、heap-buffer-overflow 之類的錯誤（名稱看陣列放在哪裡），並指出是哪一行讀寫越界。

函式	功能
`void swap_int(int a, int b)`	交換 `a` 和 `b` 的值
`void min_max(const int arr, int n, int out_min, int *out_max)`	把最小值、最大值分別寫到 `out_min`、`out_max`（一個函式「回傳」兩個值）
`int find_first(int begin, int *end, int value)`	從 `begin` 往後找，回傳第一個等於 `value` 的元素的指標
`int find_last(int begin, int *end, int value)`	從 `end` 往前找，回傳最後一個等於 `value` 的元素的指標
`long long sum_range(const int begin, const int end)`	用指標走過整段，回傳總和
`void reverse_range(int begin, int end)`	用兩個指標從兩端往中間走，搭配 `swap_int` 反轉
`void print_range(const int begin, const int end)`	輸出整段的元素，用一個空白分隔，最後換行