bzoj2792

首先想到二分答案是吧，设为lim

这道题难在判定，我们先不管将一个数变为0的条件

先使序列满足相邻差<=lim,这个正着扫一遍反着扫一遍即可

然后我们就要处理将一个数变为0的修改代价

当i变为0后，我们分别考虑左右两边的代价，对于左边

如果a[j]>(i-j)*lim的话，aj要变成a[i]+(i-j)*lim，否则的话，对于k<=j都不用变化，右边类似的道理

观察式子，a[j]>(i-j)*lim即a[j]+j*lim>i*lim,怎么做很明显了吧……

  1 var a,b,d:array[0..1000010] of longint;
  2     c,v:array[0..1000010] of int64;
  3     l,r,mx,mid,ans,i,n:longint;
  4     m,s:int64;
  5 
  6 function min(a,b:longint):longint;
  7   begin
  8     if a>b then exit(b) else exit(a);
  9   end;
 10 
 11 function max(a,b:longint):longint;
 12   begin
 13     if a>b then exit(a) else exit(b);
 14   end;
 15 
 16 function check(lim:longint):longint;
 17   var y,i:longint;
 18       s,w,t:int64;
 19   begin
 20     for i:=1 to n do
 21       b[i]:=a[i];
 22     t:=0;
 23     for i:=1 to n-1 do
 24       if b[i+1]>b[i]+lim then
 25       begin
 26         t:=t+b[i+1]-(b[i]+lim);
 27         b[i+1]:=b[i]+lim;
 28       end;
 29     for i:=n downto 2 do
 30       if b[i-1]>b[i]+lim then
 31       begin
 32         t:=t+b[i-1]-(b[i]+lim);
 33         b[i-1]:=b[i]+lim;
 34       end;
 35     if t>m then exit(0);
 36     fillchar(c,sizeof(c),0);
 37     fillchar(d,sizeof(d),0);
 38     for i:=1 to n do
 39     begin
 40       y:=min(i+b[i] div lim,n);
 41       c[y]:=c[y]+b[i]-int64(y-i)*int64(lim);
 42       inc(d[y]);
 43       if i<>1 then c[i-1]:=c[i-1]-b[i];
 44       dec(d[i]);
 45     end;
 46     s:=0;
 47     w:=0;
 48     for i:=n downto 1 do
 49     begin
 50       s:=s+c[i]+w*int64(lim);
 51       v[i]:=s;
 52       w:=w+d[i];
 53     end;
 54     fillchar(c,sizeof(c),0);
 55     fillchar(d,sizeof(d),0);
 56     for i:=n downto 1 do
 57     begin
 58       y:=max(i-b[i] div lim,1);
 59       c[y]:=c[y]+b[i]-int64(i-y)*int64(lim);
 60       inc(d[y]);
 61       c[i]:=c[i]-b[i];
 62       if i<>1 then dec(d[i-1]);
 63     end;
 64     s:=0;
 65     w:=0;
 66     for i:=1 to n do
 67     begin
 68       s:=s+c[i]+w*int64(lim);
 69       v[i]:=v[i]+s;
 70       w:=w+d[i];
 71     end;
 72     for i:=1 to n do
 73       if t+v[i]<=m then exit(i);
 74 
 75     exit(0);
 76   end;
 77 
 78 begin
 79   readln(n,m);
 80   for i:=1 to n do
 81   begin
 82     read(a[i]);
 83     s:=s+a[i];
 84     if a[i]>mx then mx:=a[i];
 85   end;
 86   if s<=m then
 87   begin
 88     writeln('1 0');
 89     halt;
 90   end;
 91   l:=1;
 92   r:=mx;
 93   while l<=r do
 94   begin
 95     mid:=(l+r) shr 1;
 96     if check(mid)>0 then
 97     begin
 98       ans:=mid;
 99       r:=mid-1;
100     end
101     else l:=mid+1;
102   end;
103   writeln(check(ans),' ',ans);
104 end.

View Code