# APCS實作題2023年10月第1題：機械鼠 > 日期：2024年1月29日 > 作者：王一哲 > 題目來源：2023年10月實作題第1題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m370) ## 題目 ### 問題描述 有 $n$ 個位置上有食物，另外有一隻老鼠一開始位於位置 $x$。 老鼠在開始覓食前要選擇今天要往左邊或往右移動去尋找食物，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。 請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。 <br /><br /> ### 輸入說明 第一行包含兩個整數：$x$ 和 $n$，以空格分隔。$x$ 代表老鼠的初始位置，$n$ 代表食物的數量。 第二行包含 $n$ 個整數，以空格分隔，表示每個食物的位置，且不會與老鼠位置重疊。 所有測試資料皆保證 $3 \leq n \leq 20$ 且 $n$ 是奇數，老鼠與食物位置範圍均為 $-100$ 到 $100$。 子題分數： - 60%：滿足 $n = 3$。 - 40%：一般情況。 <br /> ### 輸出說明 請輸出兩個整數，分別代表最多能吃到的食物數目和最後一個吃的食物停下的位置。 <br /> ### 範例輸入1 ``` 10 3 1 5 13 ``` ### 範例輸出1 ``` 2 1 ``` <br /> ### 範例輸入2 ``` 10 9 -1 13 12 16 100 -9 7 8 25 ``` ### 範例輸出2 ``` 5 100 ``` <br /> ## Python 程式碼 ### 方法1，依序讀取資料 費時最久約為 27 ms，使用記憶體最多約為 3.3 MB，通過測試。 ```python= x, n = map(int, input().split()) # 讀取初位置 x、食物數量 n pos = list(map(int, input().split())) # 讀取食物位置 left, right = x, x # 向左、右移動的終點 lsum, rsum = 0, 0 # 向左、右移動吃到的食物數量 for p in pos: # 依序由 pos 讀取食物位置 p if p > x: # 如果 p 大於 x rsum += 1 # 向右移動可以吃到的食物數量加 1 right = max(right, p) # 更新 right #if p > right: right = p # 如果 p > right，更新 right else: # 如果 p 小於 x lsum += 1 # 向左移動可以吃到的食物數量加 1 left = min(left, p) # 更新 left #if p < left: left = p # 如果 p < left，更新 left if rsum > lsum: # 如果 rsum > lsum，印出 rsum, right print("{:d} {:d}".format(rsum, right)) else: # 如果 rsum < lsum，印出 lsum, left print("{:d} {:d}".format(lsum, left)) ``` <br /><br /> ### 方法2，使用 sort 及 bisect_left 第6行是使用 bisect 函式庫中的 bisect_left，目的是要找出在已排序的 pos 之中，x 插入在何處還能維持由小到大排序，以範例輸入2為例，排序後的 pos 為 ```python [-9, -1, 7, 8, 12, 13, 16, 25, 100] ``` 若 x 為 10，則 bisect_left 回傳值 idx 為 4，因此向左可以吃到 4 個食物，向右可以吃到 5 個食物。 費時最久約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。 ```python= from bisect import bisect_left x, n = map(int, input().split()) # 讀取初位置 x、食物數量 n pos = list(map(int, input().split())) # 讀取食物位置 pos.sort() # 由小到大排序 idx = bisect_left(pos, x) # 使用二分搜尋法找 x 於 pos 插入且仍維持排序的位置 left, right = pos[0], pos[-1] # 向左、右移動的終點 lsum, rsum = idx, n-idx # 向左、右移動吃到的食物數量 print("{:d} {:d}".format(rsum, right) if rsum > lsum else "{:d} {:d}".format(lsum, left)) # 印出答案 ``` <br /><br /> ## C++ 程式碼 ### 方法1，依序讀取資料 費時最久約為 2 ms，使用記憶體最多約為 328 kB，通過測試。 ```cpp= #include <iostream> using namespace std; int main() { int x, n; cin >> x >> n; // 讀取初位置 x、食物數量 n int pos[n]; // 食物位置 for(int i=0; i<n; i++) { int p; cin >> p; pos[i] = p; } int left = x, right = x; // 向左、右移動的終點 int lsum = 0, rsum = 0; // 向左、右移動吃到的食物數量 for(int i=0; i<n; i++) { int p = pos[i]; // 依序由 pos 讀取食物位置 p if (p > x) { // 如果 p 大於 x rsum++; // 向右移動可以吃到的食物數量加 1 if (p > right) right = p; // 如果 p > right，更新 right } else { // 如果 p 小於 x lsum++; // 向左移動可以吃到的食物數量加 1 if (p < left) left = p; // 如果 p < left，更新 left } } if (rsum > lsum) { // 如果 rsum > lsum，印出 rsum, right cout << rsum << " " << right << "\n"; } else { // 如果 rsum < lsum，印出 lsum, left cout << lsum << " " << left << "\n"; } return 0; } ``` <br /><br /> ### 方法2，使用 sort 及 lower_bound 第14行是使用 algorithm 函式庫中的 lower_bound，目的是要找出在已排序的 pos 之中，x 插入在何處還能維持由小到大排序，因為回傳值為迭代器位址，如果要換算成索引值，需要再減去 vector 開頭的迭代器位址。以範例輸入2為例，排序後的 pos 為 ```cpp {-9, -1, 7, 8, 12, 13, 16, 25, 100} ``` 若 x 為 10，則 idx 為 4，因此向左可以吃到 4 個食物，向右可以吃到 5 個食物。 費時最久約為 3 ms，使用記憶體最多約為 332 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int x, n; cin >> x >> n; // 讀取初位置 x、食物數量 n vector<int> pos (n, 0); // 食物位置 for(int i=0; i<n; i++) { int p; cin >> p; pos[i] = p; } sort(pos.begin(), pos.end()); // 由小到大排序 int idx = lower_bound(pos.begin(), pos.end(), x) - pos.begin(); // 使用二分搜尋法找 x 於 pos 插入且仍維持排序的位置 int left = pos[0], right = pos[n-1]; // 向左、右移動的終點 int lsum = idx, rsum = n-idx; // 向左、右移動吃到的食物數量 if (rsum > lsum) { // 如果 rsum > lsum，印出 rsum, right cout << rsum << " " << right << "\n"; } else { // 如果 rsum < lsum，印出 lsum, left cout << lsum << " " << left << "\n"; } return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`