原题链接

题目描述

幼儿园的小孩们收到了一个有 $m$ 颗糖果的大包裹，现在要把这些糖果分给 $n$ 个小孩。

每一个小孩都给出了一个期望的糖果数，如果没有达到他的期望值 $a_i$，小孩就会生气。每差一个糖果，小孩的生气指数就会增加，可以认为他生气的程度等于他少得到的糖果数的平方。

比如，Mirko 想要得到 $32$ 个糖果，但是只得到了 $29$ 个。他少了 $3$ 个，所以他的生气指数是 $9$。不幸的是，糖果数不足以满足所有小孩的期望。所以我们应该采取最优的分配方法，使得最后小孩们的生气指数的和最小。

输入输出格式

输入格式

输入数据共 $n+1$ 行。

第一行两个整数 $m,n$。

接下来 $n$ 行，每行一个整数，第 $i+1$ 行的整数表示第 $i$ 个小朋友期望值 $a_i$。

输出格式

输出数据共一行。

一行一个整数，表示最小的总生气指数。

输入输出样例

输入1：

10 4
4
5
2
3

输出1：

4

解法

这一题首先要知道分糖果的策略，我们通过样例进行研究，将 $1$ 个糖果分给任意一个小朋友，怎样才是最优的？如果给 $a_i=5$ 的小朋友那么生气指数减少了 $5^2-4^2=9$，给 $a_i=4$ 的小朋友那么生气指数减少了 $4^2-3^2=7$ 的生气指数，以此类推，给 $i$ 号小朋友实质上生气指数会减少 ${a_i}^2-(a_i-1)^2$ 而给了一个之后 $a_i$ 就会变成 $a_i-1$ 我们只要找到每次给糖果之后生气指数减少最多的（也就是当前离目标差值最大的）就可以做了。

我拿样例来解释一下这个过程

1. 排序得到 $5,4,3,2$

2. 找到最大值 $maxn$ 为 $5$，在 $m>0$ 的情况下把所有 $a_i =maxn$ $a_i\gets a_i-1$ 同时 $m \gets m-1$

3. 找到最大值 $maxn$ 为 $4$，在 $m>0$ 的情况下把所有 $a_i =maxn$ $a_i\gets a_i-1$ 同时 $m \gets m-1$

4. 找到最大值 $maxn$ 为 $3$，在 $m>0$ 的情况下把所有 $a_i =maxn$ $a_i\gets a_i-1$ 同时 $m \gets m-1$
5. 找到最大值 $maxn$ 为 $2$，在 $m>0$ 的情况下把所有 $a_i =maxn$ $a_i\gets a_i-1$ 同时 $m \gets m-1$
6. $m=0$ 结束，计算最终和 $sum$

抽象一下

1. 排序
2. 找到最大值，所有最大值减一（满足 $m>0$）不断重复此过程
3. 计算最终和 $sum$

如果还不明白的话就看一下代码吧（注意，unsigned long long 的最大值才是 $2^{64}-1$ ）

#include <bits/stdc++.h>
using namespace std;
unsigned long long a[100005],sum,n,m,maxn,idx=1;
inline unsigned long long read()
{
    char ch=getchar();unsigned long long ret=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}
    return ret*f;
}
int main()
{
    m=read(),n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n,greater<int>());//从大到小排序
    maxn=a[1];
    while(m)
    {
        if(a[idx]!=maxn)
        {
            maxn=a[1],idx=1;
            continue;
		}
        a[idx]-=1,m-=1,idx++;
    }
    for(int i=1;i<=n;i++) sum+=a[i]*a[i];//计算最终和
    printf("%llu",sum);
    return 0;
}