[Codechef IOPC16Q][Math] Bat In Cage

原題連結
這道題....個人覺得比較傳統的數學分析。

先假設序列為有序序列(當然，可以sort，反正答案與順序無關)
一個先備的結論是如果我們只取一個x使得他到所有點距離和最短，答案會是中位數。

再來，對於本題講一個結論：
1. 最優解的x,y必定會將此序列分成兩半，其中一半是x取得最小值，另一半是y取得最小值。

有了這個結論就比較容易做了。我們枚舉x和y取得最小值的交界點，然後試著計算答案。
WLOG，設x瓜分左半邊序列1~M，y瓜分右半邊序列M+1~n，目標是要在O(1)內計算出此次的花費。

根據先備結論，我們只需要找到兩邊序列的中位數然後去計算就好了。當然，需要一點數學分析和前綴和思想，不過並不難實做，可以自己練習。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=1000000+5;
const LL INF=(1LL<<60);
LL pre[maxn],a[maxn];
int main()
{
    LL T;
    scanf("%lld",&T);
    while(T--)
    {
        LL n,ans=INF;
        scanf("%lld",&n);
        for(LL i=1;i<=n;i++) scanf("%lld",a+i);
        sort(a+1,a+n+1);
        for(LL i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
        for(LL M=1;M<=n;M++)
        {
            LL xp=(1+M)/2,yp=(M+1+n)/2,x=a[xp],y=a[yp];
            ans=min(ans,(((xp-1)*x-pre[xp-1]) + (pre[M]-pre[xp]-(M-xp)*x))+
            (yp-M-1)*y-(pre[yp-1]-pre[M]) + (pre[n]-pre[yp]-(n-yp)*y));
        }
        printf("%lld\n",ans);
    }
}