金组的神题喵。。
[题目描述]
给你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.