TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4852
  • Problem
  • P4852糖果
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,256m
    Description

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

    Input Format

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

    Output Format

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

    Sample Input 1

    10 4
    4
    5
    2
    3

    Sample Output 1

    4

    Sample Input 2

    5 3
    1
    3
    2

    Sample Output 2

    1

    Hint

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

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


    Source  克罗地亚公开赛10-11