[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];
      nth_element(arr, arr+(n>>1), arr+n);
      int mid;
      if(n&1) mid=arr[n>>1];
      else{
         nth_element(arr, arr+((n>>1) - 1), arr+n);
         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;
}