[TIOJ] 1732. 買當勞
題目連結: http://tioj.infor.org/problems/1732 應該不難發現買當勞要建的位置就是所有資料的中位數，所以就排個序就可以找到了，複雜度$O(n log n)$ #include <bits/stdc++.h>
using namespace std;
#define N 100000
int arr[N+5];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;
while(cin>>n){
for(int i=0;i<n;i++) cin>>arr[i];
sort(arr, arr+n);
int mid;
if(n&1) mid=arr[n>>1];
else mid = (arr[n>>1]+arr[(n>>1) - 1])>>1;
int ans=0;
for(int i=0;i<n;i++) ans+=abs(arr[i]-mid);
cout<<ans<<'\n';
}
return 0;
} 不過突然看到聖福學長用超快的作法過了這題，想了三十秒才發現其實根本可以用nth_element做到$O(n)$的複雜度 #include <bits/stdc++.h>
using namespace std;
#define N 100000
int arr[N+5];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;
while(cin>>n){
for(int i=0;i<n;i++) cin>>arr[i];
...