【APCS】2023年10月實作題 C++ 解題筆記（第一題）

此筆記僅供個人學習用途，內容僅供參考。

  1. https://zerojudge.tw/ShowProblem?problemid=m370

題目說明：

n 個位置上有食物，有一隻老鼠剛開始位於位置 x，覓食時只能往左或往右一個方向，試問找出最大能吃多少食物，並且最後一次吃食物停下的位置。

解題思路：

  1. 建立 vector <int> f(n + 1)，並把 x 丟進去 f 裡面，順序不重要，丟進去就好。
  2. 輸入完所有的 f 後，再進行排序。
  3. 使用 auto it = find(f.begin(), f.end(), x); 找出 x 的索引值。
  4. 計算從 x 到最小索引值跟最大索引值的距離，取 max() 得出最多能吃多少食物。
  5. 最後透過 f[0] 跟 f.back() 分別取得最後的位置。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>

using namespace std;

int main(){
    int x, n;
    cin >> x >> n;
    
    vector<int> f(n + 1);
    f[n] = x; // 可任意，反正最後排序都沒差
    
    for (int i = 0; i < n; i++){
        cin >> f[i];
    }
    
    sort(f.begin(), f.end());
    
    auto it = find(f.begin(), f.end(), x); // 找 x 索引值
    
    int min_f = distance(f.begin(), it); // 用 distance(f.begin(), it) 計算最小索引值到 x 的距離（能吃多少食物）
    int max_f = n - min_f; // 用長度 - min_f 可得出最大索引值與 x 的距離
    
    // 後面使用三元運算子判斷要輸出哪一個最終位置
    cout << max(max_f, min_f) << " " << (max_f > min_f ? f.back() : f[0]);
    return 0;
}