题解 P4409 【[ZJOI2006]皇帝的烦恼】

这题怎么没有pascal题解啊qaq

那蒟蒻就发一篇吧

感觉这是道恶评题(应该只有黄吧)

如dalao所说，这题就是一个二分，因为有单调性，所以可以直接二分答案，然后再判断答案是否可行即可。

用b[i]表示第i个数与第一个数最多可以相同多少个，c[i]表示第i个数与第一个数至少相同多少个,所以只要判断c[n]是否为0即可

代码：

uses math;
var
  a,b,c:array[0..100005] of int64;//小心longint不够存哦(虽然这题似乎不会)
  i,j,n,ll,rr,mid:longint;
function check(mid:longint):boolean;
var
  i:longint;
begin
  for i:=2 to n do
  begin
    b[i]:=min(a[i],a[1]-c[i-1]);
    c[i]:=max(0,a[1]+a[i-1]-b[i-1]+a[i]-mid);
  end;
  if c[n]=0 then exit(true) else exit(false);
end;//验证答案是否可行
begin
  readln(n);
  for i:=1 to n do
  begin
    read(a[i]);
    ll:=max(ll,a[i]+a[i-1]);
  end;
  b[1]:=a[1];
  c[1]:=b[1];
  rr:=300000;//rr代表查找上界,ll代表查找下界
  while ll<=rr do
  begin
    mid:=(ll+rr)>>1;//>>1相当于/2，但>>1更快
    if check(mid) then rr:=mid-1 else ll:=mid+1;//更新上下界
  end;//二分答案
  writeln(ll);
end.