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後的數字
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
|
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];
else if(num%2==0) cout<<(x[num/2]+x[(num/2)+1])/2;
cout<<"\n";
num++;
}
return 0;
}
|
UVa 10107 - What is the Median?
