UVa 10107 - What is the Median?

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

題目會一個一個地持續輸入新的數字，而我們需要輸出 到目前為止已輸入的數的中位數

  • 中位數即在一連串已由小到大排序的數字中，排在中間的那一個數。例如：
    8、9、10、11、12 的中位數為 10
    2、3、3、5、7、10 的中位數為 4

Step 2. 解題思路

  • 每次在輸入後便對數列進行排序
  • 若當前數字數量為奇數，則輸出位於正中間的數
  • 若當前數字數量為偶數，則輸出由正中間兩數除以2後的數字

Step 3. 範例輸入與輸出 - Sample Input and Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
15 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
15 3
15
9
3
6
12
13
7
1
4
10
11
5
2
8
14
0 0

Extra Sample Input
Extra Sample Output

uDebug 快速連結
Diffnow (線上比對程式)
C++ Online Compiler
Python Online Compiler

Step 4. 參考程式碼 - Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int x[10001],num=1;
    while(cin>>x[num]) {
        sort(x,x+num+1);
        if(num==1) cout<<x[1];
        else if(num%2!=0) cout<<x[(num/2)+1];   //num is odd
        else if(num%2==0) cout<<(x[num/2]+x[(num/2)+1])/2;  //num is even
        cout<<"\n";
        num++;
    }
    return 0;
}