a941 - 10041 - Vito's large family
題目描述
題目描述了黑社會老大 Vito Deadstone 要搬到紐約，並希望找到一個位置，使得他到所有親戚家的距離和最小。親戚數量可能很大，且可能有多個親戚住在同一地址。要求輸出最小距離和以及 Vito 的新家地址（如果有多個地址能達到最小距離和，則輸出最小的地址）。
解題思路
本題的核心思想是尋找一個中位數作為 Vito 的新家地址。這是因為到所有親戚的距離和最小，等價於找到一個數，使得所有親戚到這個數的絕對差的和最小。這個數就是親戚地址的中位數。
- 統計地址出現次數： 使用一個陣列
a統計每個地址出現的次數。 - 計算中位數： 由於親戚數量
r可能為奇數或偶數，因此需要處理兩種情況。- 如果
r是奇數，中位數就是排序後位於中間位置的地址。 - 如果
r是偶數，中位數可以取排序後中間兩個地址的其中一個（通常取較小的）。程式碼中將r調整為r+=r%2; r/=2;，實際上是將偶數的r變成r+1再除以 2，也就是取了較小的中位數。
- 如果
- 計算最小距離和： 遍歷所有地址，計算每個地址出現次數乘以到中位數的絕對距離，並將結果累加到
total中。 - 輸出結果： 輸出
total和中位數ans。
複雜度分析
- 時間複雜度: O(N + M)，其中 N 是親戚數量 (r)，M 是地址範圍 (30001)。主要時間花在統計地址出現次數和計算最小距離和的迴圈上。
- 空間複雜度: O(M)，主要用於儲存地址出現次數的陣列
a。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <math.h>
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long int x) {
if(x==0)
putchar_unlocked('0');
else{
long long int stk[40],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
long long int t=read(),r;
while(t--){
r=read();
long long int a[30001]={0},x,ans=0,total=0;
for(int i=0;i<r;++i){
x=read();
++a[x];
}
r+=r%2;
r/=2;
x=0;
while(1){
x+=a[ans];
if(x>=r)break;
++ans;
}
for(int i=0;i<=30000;++i)
if(a[i])total+=labs((ans-i)*a[i]);
write(total);
putchar_unlocked(' ');
write(ans);
putchar_unlocked('\n');
}
}