10107 What is the Median?

題目敘述

每當讀入一個新整數後，就必須馬上輸出目前所有數字的中位數。

輸入說明

輸入包含了N個（N<10000）的整數。

輸出說明

對每一個輸入，請輸出到現在為止已輸入的數的中間數。

解題思路

如果目前總數是奇數，則中位數是排序後的中間那個數。
如果目前總數是偶數，則中位數是中間兩數的平均值，直接取整數。

程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long n;
  vector<long long> arr;

  while (cin >> n) {
    arr.push_back(n);

    // 每次輸入後即時排序
    sort(arr.begin(), arr.end());

    // 根據目前元素數量輸出中位數
    if (arr.size() % 2 == 0) {
      // 偶數個 → 取中間兩數的平均（只取整數部分）
      cout << (arr[arr.size() / 2 - 1] + arr[arr.size() / 2]) / 2 << endl;
    } else {
      // 奇數個 → 取中間的數
      cout << arr[arr.size() / 2] << endl;
    }
  }
}