# 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++`
Sign in with Wallet
Connect another wallet