題目請參考 https://zerojudge.tw/ShowProblem?problemid=f376.
這題的答案就是在找一個數字V可以得到min(∑|ai-V|),i=1~n, 所以答案V就是ai的中位數.
我們只要先把數字ai排序好,找出中位數印出來就可以了.
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
//排序
std::sort(a, a+n);須注意n是奇數或偶數時的中位數index不一樣,所以要分開處理.
if(n&1){//n是奇數
printf("%d",a[n/2]);
}else{ //n是偶數
printf("%d",a[n/2-1]);
}完整程式如下,AC需時19ms.
#include <iostream>
#include <algorithm>
using namespace std;
int a[100000];
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
//排序
std::sort(a, a+n);
if(n&1){//n是奇數
printf("%d",a[n/2]);
}else{ //n是偶數
printf("%d",a[n/2-1]);
}
return 0;
}
