P6236 [COCI2010-2011] LJUTNJA

原题链接

题目描述

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

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

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

输入输出格式

输入格式

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

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

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

输出格式

输出数据共一行。

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

输入输出样例

输入1:

1
2
3
4
5
10 4
4
5
2
3

输出1:

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$ )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}
文章作者: answerend42
文章链接: http://answerend42.github.io/2020/03/25/lg6236/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog