pascal题目：游戏

pascal题目：游戏

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

一开始我是这么想的：

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

    如果给第一个人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.

或者直接从附件中下载。