Question

pascal题目

校庆到了，每个学生都有礼物，礼物就是糖，现在有M块糖，分给N个学生，每个学生心目中都有个理想数量，如果学生分到的数量没有想的多，他就会生气，生气指数等于X^2(X为缺少的数量)，例如Alice心中理想数量为32，结果分到29，他的生气指数为(32-29)^2=9。
不幸的是，糖的总数总是不够分，请你帮忙设计一个分配方案使得计算生气指数之和最小。
Input
第一行包含两个整数:M(1<=M<=2*10^9)和N(1<=N<=100000)。
接下来N行，每行包含一个整数表示每个学生心目中的理想糖数，每个数保证小于2*10^9，而且总和一定会超过M。
Output
输出一个整数表示最小的生气指数之和。
保证结果在int64范围内。
Sample Input Copy
5 3
1
3
2
Sample Output Copy
1

Answer 1

这题也许是贪心算法的一个简单应用 。

一开始我是这么想的：

但是马上就推翻了这种简单的算法：

    如果给第一个人7颗糖，第二个人3颗，那么生气指数是：

                             

尽管上述看似对于解题没太大帮助，但是了解一个思考过程我觉得也是有必要的。

事实上，它启发了我找到下面这个应该正确的算法。

——————————————————————————————————————

36，比一开始的55小了很多。

事实上，经过验证，36是这一个例子中最小的结果。

（用以上算法验证一下样例，得到的也是正确答案）

      贪心的算法一旦确定，代码应该就好写了。

      目前摆在面前的一道坎，是数据范围。那么大的数，一个个减去一定会超时，因此用了一点技巧。

写了很久的代码，看一下：

var a:array[1..100000]of record
                                         x,y:longint;          //记录类型，x表示理想糖数，y表示实际收到糖数；
                                       end;
    s,ans:int64;
    m,n,i,j,t:longint;

procedure sort(l,r:longint);            //快速排序，从小到大；
var i,j,k,t:longint;
begin
 i:=l; j:=r; k:=a[(l+r) div 2].x;
 repeat
  while a[i].x<k do inc(i);
  while a[j].x>k do dec(j);
  if i<=j then
  begin
   t:=a[i].x; a[i].x:=a[j].x; a[j].x:=t;
   inc(i); dec(j);
  end;
 until i>j;
 if i<r then sort(i,r);
 if l<j then sort(l,j);
end;

begin
 readln(m,n);
 for i:=1 to n do
 begin
  readln(a[i].x);
  a[i].y:=a[i].x;
  inc(s,a[i].x);
 end;
 sort(1,n);
 for i:=1 to n do a[i].y:=a[i].x;

 i:=0;
 while true do
 begin
  inc(i);
  t:=a[i].y;
  while (s-t*(n-i+1)<m) and (t>0) do
   dec(t);
  dec(s,t*(n-i+1));
  if t>0 then for j:=i to n do dec(a[j].y,t)
           else break;
 end;                                                          //代码核心；

 while s>m do
 begin
  dec(a[i].y);
  inc(i);
  dec(s);
 end;

 for i:=1 to n do
  inc(ans,trunc(sqr(a[i].x-a[i].y)));
 writeln(ans);                                            //最终结果；

 readln;
end.

或者直接从附件中下载。