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; // 否則決定往右邊走
}
