ZeroJudge 解題筆記：f376. 芝麻街的團購

作者：王一哲
日期：2025年10月8日


ZeroJudge 題目連結：f376. 芝麻街的團購

解題想法

這題的測資不大，可以真的計算以每個點為中心的總距離，再找其中的最小值。實際上答案就是取中位數。

Python 程式碼

使用時間約為 0.3 s，記憶體約為 19 MB，通過測試。

n = int(input())
psum = [0] + list(map(int, input().split()))
psum.sort()
for i in range(1, n+1): psum[i] += psum[i-1]
imin = float('inf')
ans = 0
for i in range(1, n+1):
    dis = (2*i-n-1)*(psum[i] - psum[i-1]) - psum[i-1] + psum[n] - psum[i]
    if dis < imin:
        imin = dis
        ans = psum[i] - psum[i-1]
print(ans)

使用時間約為 0.1 s，記憶體約為 16.6 MB，通過測試。

n = int(input())
arr = sorted(list(map(int, input().split())))
print(arr[n//2] if n%2 else arr[n//2 - 1])

C++ 程式碼

使用時間約為 18 ms，記憶體約為 464 kB，通過測試。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int arr[n];
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    sort(arr, arr+n);
    if (n%2) printf("%d\n", arr[n/2]); 
    else printf("%d\n", arr[n/2 - 1]);
    return 0;
}