e511 - 11364 - Parking
題目描述
題目要求找到一條直線上多個商店的最佳停車位置，使得總步行距離最小。給定商店的位置，需要計算出最佳停車位置與最遠商店和最近商店之間的距離總和。
解題思路
這題的解法是使用貪心策略。首先，讀取商店的數量 n，然後讀取每個商店的位置 xi。接著，找到商店位置的最大值 a 和最小值 b。最佳停車位置位於最大值和最小值之間，使得總步行距離最小。總步行距離為 (a - b) * 2。如果只有一個商店，則步行距離為 0。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#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>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0){
putchar_unlocked('0');
return;
}
int stk[5],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int n,tmp,t=read();
while(t--){
n=read();
int a=0,b=100;
if(n==1){
tmp=read();
putchar_unlocked('0');
}
else{
while(n--){
tmp=read();
(tmp>a)?a=tmp:0;
(tmp<b)?b=tmp:0;
}
write((a-b)*2);
}
putchar_unlocked('\n');
}
}