金组的神题喵。。

[题目描述]

  给你N个数，第一个和最后一个不能去掉。

现希望去掉中间某段连续的数，使得剩下的数的平均值最小化。

之前已经做了很久，一直想不到正解。。然后去网上查，发现没有。。

又去USACO上看官方题解，发现看不懂喵。。

然后很绝望地问了杜教。。

结果杜教很鄙视地只回了一句话。。

然后我就很不知天高地厚地D了杜教

后来杜教再很无奈地

哎。。。。。

妈蛋自己之前只想着二分长度什么的。。没想到二分答案

哎自己这么弱连杜教都拯救不了自己。。

这么弱搞什么OI。。

那么接下来给出一个正式的题解。。

       二分答案，然后对于每一个Ai-=c

       对这个序列的第2项到第n-1项求最长字串。。

      设这个值是max,那么可以得到 max+x(即前面的那一段的和)+y(即后面的那一段和)=all-c*n，all是原数列和

       x+y=all-ans*n-max

       如果x+y<=0，那么这个c就是合法的。。

      完毕。。

[反思]

          其实之前想的和这个很相近，只是没有往二分上想。。

          知识运用不够灵活。。

         而且之前推到出来的公式和上面的差不多，就想着怎么让x+y最小，，就想出了很多神奇搞法。。

Code：

const shuru='sabota.in';shuchu='sabota.out';maxn=100000;INF=1 shl 25;
var	a:array[0..maxn] of longint;b:array[0..maxn] of extended;step,all,i,j,k,n:longint;mid,p,data,ans,left,right:extended;
function big(a,b:longint):longint;
beginif a>b then exit(a);exit(b);
end;
procedure init;
beginreadln(n);for i:=1 to n do begin readln(a[i]); inc(all,a[i]); step:=big(step,a[i]); end;
end;
function max(a,b:extended):extended;
beginif a>b then exit(a);exit(b);
end;
function min(a,b:extended):extended;
beginif a<b then exit(a);exit(b);
end;
function gotmax:extended;
var i:longint;ans:extended;
begingotmax:=0;ans:=-INF;for i:=2 to n-1 dobegingotmax:=gotmax+b[i]; ans:=max(ans,gotmax);if gotmax<0 then gotmax:=0;end;exit(ans);
end;
procedure main;
begininit;left:=0;right:=step;ans:=INF;repeatmid:=(left+right)/2;for i:=1 to n do b[i]:=a[i]-mid;data:=gotmax;p:=all-mid*n-data;if p<=0 then beginright:=mid-0.0000001;ans:=min(ans,mid);endelse left:=mid+0.0000001;until right-left<0.00001;if ans=INF then writeln(2.000:0:3)else writeln(Ans:0:3);
end;
beginmain;
end.