TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4852
  • 题目
  • P4852糖果
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,256m
    问题描述

    信竞队的同学们收到了一个糖果礼包,里面有M颗糖。
    何老板现在要把这些糖果分给N个同学。
    每一个同学都给出了一个期望得到的糖果数,如果没有达到他的期望值a[i],该同学就会生气。每差一个糖果,同学的生气指数就会增加。他生气的程度等于他少得到的糖果数的平方。
    比如,nanstop想要得到12个糖果,但是只得到了9个。他少了3个,所以他的生气指数是9。
    但是,糖果数不足以满足所有同学的期望。所以何老板打算应该采取最优的分配方法,使得分配后同学们的生气指数之和最小。

    输入格式

    第1行:2个整数M,N
    第2..N+1行:第i+1行表示第i个同学的期望值a[i]

    输出格式

    第1行:1个整数,表示最小的生气指数总和

    样例输入 1

    10 4
    4
    5
    2
    3

    样例输出 1

    4

    样例输入 2

    5 3
    1
    3
    2

    样例输出 2

    1

    提示

    \(1 ≤ N ≤ 100,000,1 ≤ M ≤ 2*10^9,M < \sum{a[i]}\)

    结果不超过 $2^{64}-1$


    来源  克罗地亚公开赛10-11