機械鼠

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

題意

數線上有一隻老鼠
且有 $n$ 個食物散落在數線上
老鼠可以選擇一直往左或一直往右
求最多可以吃到幾個食物及最後吃食物的位置

想法

把問題轉換一下
就變成是在問老鼠左邊還是右邊食物比較多、最左邊或最右邊的食物在哪裡
於是只要簡單維護一下就可以幾個變數就可以解出來了

考點

• 主要考點
  • C++ 的程式結構
  • 變數的使用方式
  • 條件判斷
  • 基本運算
  • 基本輸入
  • 基本輸出
  • 數學函式
  • While 迴圈

程式碼

#include <bits/stdc++.h>

using namespace std;

int main() {
    int x, n, tmp;
    cin >> x >> n;
    int cntl = 0, cntr = 0; // 左邊與右邊食物數量
    int maxv = -1e5, minv = 1e5; // 用最大與最小值維護最後停在的食物位置
    while (n--) {
        cin >> tmp;
        if (tmp >= x) cntr++; // 如果食物在左邊
        if (tmp <= x) cntl++; // 如果食物在右邊
        maxv = max(maxv, tmp);
        minv = min(minv, tmp);
    }
    if (cntl > cntr) cout << cntl << " " << minv << endl; // 往做邊走解更優
    else cout << cntr << " " << maxv << endl; // 否則決定往右邊走
}