Description
给你N个长2高h的矩形的质量mi，这N个矩形被放置在笛卡尔坐标系中：
1.矩形的四条边平行于坐标轴；
2.每个矩形下面的水平边的y坐标值互不相同，分别是0,h,2h,3h,…,(N-1)h；
3.最下面的矩形的左下角坐标为(-2,0)，即右下角在原点处。
一种矩形的摆放方式是稳定的，当且仅当满足：每个矩形上面的所有矩形的x重心跟该矩形的x中点相距不超过1。上面左图是不稳定的而右图是稳定的。
给你N个矩形的质量，要求在不改变矩形的上下顺序的前提下找到一种稳定的摆放方式，同时输出所有稳定摆放方式中最右边矩形右下角x坐标的最大值。
Input
第一行输入矩形的数量N(2<=N<=300,000)
接下来N行按照从下到上的顺序输入每个矩形的质量。
Output
输出所有稳定摆放方式中最右边矩形右下角x坐标的最大值。输出与答案相差不得超过0.000001。
Sample Input
输入1：
2
1
1
输入2：
3
1
1
1
输入3：
3
1
1
9
Sample Output
输出1：
1.000000
输出2：
1.500000
输出3：
1.900000
Data Constraint
30%的数据保证矩形的质量从下到上逐渐减小。
题解
这题直接做是不好做的。
从答案构成方法下手。
我们有上面的图可以大致推测——答案是长">"样子的。
那么答案必定是某个方块向右边突出来一段，并且保证重心在-2~0之间。
那么我们考虑如何求出一个方块上面的重心。
根据式子，我们发现，由于最顶上的方块没有限制，于是这意味着我们可以随意控制当前i上方所有方块重心位置。
我们画个图理解理解：
分两种情况——
1、当i为最右边的方块时，由于我们要保证i-1的重心在合法范围内，并且让i尽量往右。
那么我们设r[i]表示第i个方块右端点的坐标为r[i]，M[i]表示n~i的m总和
那么
意思就是说当把i+1以上的方块重心压在i左端点时i-1的右端点位置最右可到哪。
然后化一下式子可以得到r[i]的最右端点。
记录答案即可。
2、当i不为最右边的方块时，那么就要求尽量往右边放。
当然也要保证r[i-1]合法
于是
意思就是把上面的重心放在r[i]时，可最大化之后右端点的答案。
以此来更新r[i]即可。
var
i,j,k,n:longint;
l,ans:extended;
m:array[1..300000] of longint;
sum:array[1..300001] of longint;
r:array[1..300000] of extended;
begin
readln(n);
for i:=1 to n do
begin
readln(m[i]);
end;
for i:=n downto 1 do
begin
sum[i]:=sum[i+1]+m[i];
end;
r[1]:=0;
for i:=2 to n do
begin
ans:=max(ans,(r[i-1]*(sum[i])+2*sum[i+1]+m[i])/(sum[i]));
r[i]:=(r[i-1]*(sum[i])+m[i])/(sum[i]);
end;
writeln(ans:0:6);
end.