CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=e606
內容
給定一個數列，找出一個整數 A 使得到數列上每個點的距離和為最小。
每組測資第一列為數列長度 n (0 < n <= 1000000)，接著為數列。
依序輸出
1. 最小的 A。
2. 輸入中有多少個數與 A 有相同性質。
3. 有幾種可能的 A。
範例輸入
2
10
10
4
1
2
2
4
範例輸出
10 2 1
2 2 1
想法
排序後，若此數列長度為奇數，令 L = R = 中位數，若為偶數，令 L 跟 R 分別為中間兩點。
此時 L 為最小的 A ， R - L + 1 為 A 的數量。
接著遍歷一次數列即可知道輸入中有多少個數與 A 有相同性質(找數列中介於 L 與 R 之間的數)。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int mp[1000001];
int main(){
fastio;
int n, L, R, A, num;
while(cin >> n){
A = 0;
for(int i = 0; i < n; ++i) cin >> mp[i];
sort(mp, mp + n);
if(n & 1){
L = mp[n >> 1];
R = L;
}
else {
L = mp[(n >> 1) - 1];
R = mp[n >> 1];
}
num = R - L + 1;
for(int i = 0; i < n; ++i){
if(mp[i] > R) break;
if(mp[i] >= L && mp[i] <= R) ++A;
}
cout << L << " " << A << " " << num << "\n";
}
}
|