题解 P2985 【[USACO10FEB]吃巧克力Chocolate Eating】

· · 题解

我们利用二分答案和贪心来解决这道题目。

当然要注意，数据大于longint，可以用int64，用qword也可。

var n,d,i,j:longint;
    sum,l,r,mid,ans,x:qword;
    a,b,c:array[1..50001]of qword;//a数组储存的是原始数据，b数组储存的是当前二分答案时的分配方案，c数组储存的是最后答案的分配方案。
    bo:boolean;//哨兵
begin
  readln(n,d);//读入数据
  for i:=1 to n do 
    begin
      readln(a[i]);
      r:=r+a[i];//将r算出来，r可以到所有值的和，因为可以在一天将所有巧克力都吃了。
    end;
  while l<=r do
    begin
      mid:=(l+r) div 2;//算出mid，就是当前我们尝试到的答案。
      bo:=true;//初始化。
      ans:=0;//记录高兴度。
      j:=1;//从第一个巧克力开始。
      for i:=1 to d do
        begin
          ans:=ans div 2;//根据题意，睡了觉，高兴度下降一半。
          while ans<mid do //当前的高兴度还未满足当前尝试的答案。
            begin
              ans:=ans+a[j];//加上当前巧克力的高兴度。
              b[j]:=i;//将当前的巧克力分配给当前一天。
              j:=j+1;//进入下一个巧克力。
              if j>n+1 then //巧克力若分配完了
                begin
                  bo:=false;//标记哨兵
                  break;//退出循环，再做下去不存在意义
                end;
            end;
          if not bo then break;
        end;
      if bo then//若为真，说明当前尝试的答案是可以被满足的。
        begin
          x:=mid;//记录答案
          for i:=j to n do b[i]:=d;//若最后的几块巧克力还没被吃掉，就都分配给最后一天。
          l:=mid+1;//尝试的答案可以变大
          for i:=1 to n do c[i]:=b[i];//将分配方案给答案
        end else r:=mid-1;
    end;
  writeln(x);
  for i:=1 to n do writeln(c[i]);
end.