牛客多校第一场C题Euclidean Distance水解

题目链接：

https://ac.nowcoder.com/acm/contest/881/C

题目大意：

给定一个N维坐标系的点A（a1/m,a2/m,a3/m,...,an/m），寻找一个点P(p1,p2,p3,...,pn)满足p点的各坐标之和为1，且p1,p2,p3,...,pn > 0，使得A点到P点的欧几里得距离最小，其中A与P之间的欧几里得距离即为，求这个最小的欧几里得距离，若为分数则用分数形式表示。

思路：

首先将分母的m处理掉（记在分母），我们先将所有坐标放大m倍 = m , A(a1,a2,a3,...,an),接下里我们转换一下问题，首先对A的坐标从大到小排个序，然后我们来看一下这张图（先画八个吧后面自己脑补） ，
这是排序后的A的坐标们，我们现在需要确定P的坐标，也就是将-m（因为在欧几里得距离中A和P的坐标是直接相减关系）分配到这个图里，不难证明按照如下方法来分配效果最佳，
以下给出简答说明：我们要使得减去pi后的ai平方和最小，那么是ai中较大的数减小的收益一定比使较小的数（负的不就更小么，收益为负）变小的收益大，那么我们的第一次操作如图，将A1推平到与A2一样，为什么不继续往下推呢？因为我们接下来要连A2一起推！（否则A2也是较大不推血亏），同理，当我们的m剩余量还够时，我们就直接将A1，A2推平到A3,那么如图，加入当我们需要将A1,A2,A3,A4推平到A5时，我们的m不够用了，我们只需要将他们整体往下尽可能的推就行了，依然不难证明，参差不齐的推收益更小。
那么我们要做的就是维护一个前缀，并不断修改，前缀和m了，虽然这样很好懂，但其实这样，还是麻烦了！
上面说到了我们每次推平前i个是最优，这确实没错，但我们看看最后的状态，我们既然推平了前面的所有，那为何不一步推到位呢？我们只需要排序后记录前缀和，然后考虑到哪里前缀和减去m平不下去了，我们就推到哪里！
（这里应要求加上了样例3 10 1 -2 3 的情况，领会一下吧，）
那么代码如下，欢迎大家提出意见：

#include <cstdio>
#include <algorithm>
#include <cstring>
#define Maxn 100008
using namespace std;
typedef long long ll;

ll n,m;
ll a[Maxn],sum[Maxn];

ll gcd(ll a,ll b){ return (!b) ? a : gcd(b,a%b);}

bool cmp(ll a,ll b){    return a > b;}

int main()
{
    while(scanf("%lld%lld",&n,&m) != EOF)
    {
        ll ansa,ansb,now = n;//now表示能够推平到的位置，ansa记录分子，ansb记录分母
        for(ll i = 1;i <= n;i ++ ) scanf("%lld",&a[i]);
        sort(a+1,a+n+1,cmp);
        sum[0] = -m;
        for(int i = 1;i <= n;i ++) sum[i] = sum[i - 1] + a[i];//前缀和
        for(int i = 1;i < n;i ++)
        {
            if(sum[i] > a[i+1] * i)
            {
                now = i;
                break;
            }
        }
        ansa = sum[now] * sum[now] * now;
        ansb = now * now;
        for(ll i = now + 1;i <= n;i ++)
                    ansa += a[i] * a[i] * ansb;
        ansb *= (m * m);
        ll gd = gcd(ansa,ansb);
        ansa /= gd,ansb /= gd;
        if(ansb == 1 || (!ansa)) printf("%lld\n",ansa);
        else printf("%lld/%lld\n",ansa,ansb);
    }
    return 0;
}

给没看懂代码中分子ansa = sum[now] * sum[now] * now;的处理的同学下面一个简单说明：我们既然推平了前now项，那么每一项为sum[now] / now，平方后为(sum[now]/now)^2,由于有now项，我们需要再乘一个now，于是分子就变成了sum[now] * sum[now] * now