C.最优公式瞎搞题解

菜逼选手比赛时想不到切比雪夫距离转曼哈顿怎么办呢？可以通过对该题目的一步步分析得到一个仅仅适用于本题的特殊解法（而且跑的速度贼快）。

首先分析题目的性质，可以从仅有两个点的特例看起，设两个点分别为x,y，容易发现只需要a,b分别位
x,y中点两侧且距离中点相等即可取得最小值。题目中样例答案a=b,那么我们大胆猜测，必定存在一个解使a=b。

现在尝试小心验证：设已有答案(a,b),可以构造新答案,原答案与题目中的每对组合的相对位置，可能产生3种情况(已去除对称情况）：xyab,xayb,axyb,xaby（在第三、四种情况中默认a，b中点位于x，y中点右侧，若不满足可将顺序翻转）。这三种情况中，计算过程中的最大值均为，而在新答案中该最大值稳定减小了，同时，另一组对答案的贡献的变化也不超过,因此答案总体减小或不变，由于原有答案已经为最小值，因此新答案依然成立。

当我们将题目化简为只需取一个位置时，遵循以上中点的思路，可以发现，我们在移动该位置时，若该位置的移动过程中不跨过某一对数对的中点，那么这次移动对该数对答案的影响即为移动长度d*2，例如从数对（1，5）的中点3向右移动1，（1，5）对总体答案的贡献就增加了2，若从4移向3，则贡献减少2。我们可以假设我们每次从某个数对的中点移向右边下一个数对的中点，该过程不跨过其他任何中点，那么就有一部分数对答案增加，另一部分减少，而跨过中点时两种情况数对的数量发生变化。

容易发现，增加的数对均为中点在答案位置左边的数对，减少的数对均为中点在答案位置右边的数对，因此移动过程答案的变化是先减后增，所以可以直接二分出答案位置，也可使用双指针之类的算法取所有数对中点的中位数的位置作为答案。

代码：

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1e5+500,M=1e9+7;
typedef long long ll;

int gti(void)
{
    char c=getchar();
    int ret=0,st=1;
    for (;c!='-'&&!isdigit(c);c=getchar());
    if (c=='-') st=-1,c=getchar();
    for (;isdigit(c);c=getchar()) ret=ret*10+c-'0';
    return ret*st;
}

int n,a[N];
ll calc(int x)
{
    int l=1,r=1,cnt=1;
    ll ret=0,now;
    while (l<=n&&a[l]<x) ++l;
    r=l,l--;
    while (cnt<=n)
    {
        if (!l) now=a[r]-x,r++;
        else if (r>n) now=x-a[l],l--;
        else if (x-a[l]<a[r]-x) now=x-a[l],l--;
        else now=a[r]-x,r++;
        ret+=now*(cnt*2-1),++cnt;
    }
    return ret;
}

int main(void)
{
    n=gti();
    for (int i=1;i<=n;i++) a[i]=gti()*2;
    sort(a+1,a+1+n);
    int l=2,r=1e9;
    ll ans=8e18;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        ll ans1=calc(mid),ans2=calc(mid+1);
        if (ans1>ans2) ans=min(ans,ans2),l=mid+2;
        else ans=min(ans,ans1),r=mid-1;
    }
    printf("%lld\n",ans%M);
    return 0;
}