题解 P1181 【数列分段Section I】

野菜汤 · 2013-08-28 23:25:17 · 题解

题解：

其实这题很容易啦，只要一个循环过去，然后将数字相加，如果超过界限就分组，然后只要数组开的够大，基本通过就不是问题啦！以下是个人的源程序代码，仅供参考。

var i,m,n,ans,sum:longint;
    a:array[1..100000] of longint;
begin
  read(m,n);
  sum:=1;{因为从第一个开始就算是一组了，但是一次划分之后就算有了两组，所以初始化值为1}
  for i:=1 to m do read(a[i]);
  for i:=1 to m do begin
    ans:=ans+a[i];
    if ans>n then begin inc(sum);ans:=a[i];end;//如果ans超过标准，那么总数sum加1，ans就直接等于那个数（也就是分组了）
  end;
  write(sum);
end.

这是一道比较经典的贪心练手题，很简单，却包含了贪心的精华，贪心并不是一种固定模式的算法，而是需要技巧的求其最优解，所以对个人的思考有着较深的要求。