题目
题目大意
有一堆长为222的矩形，最下面的右端点横坐标为000。
每个矩形都有其固定的质量。
将这些矩形堆在一起，使得最右边的横坐标最大，并且满足它不会塌掉（满足物理学）。
思考历程
首先就觉得这是一道结论题。
这个东西看起来不可以DP做，所以就往贪心的方面想。
我想从上往下推过来，计算出可能的最左和最右的重心的位置。
在计算的时候记录一下最右边的点。
实际上我的这个想法存在着太多的漏洞，以至于我连样例也没有过。
正解
首先，最优的方案一定是长成“>>>”形状的。
接下来我们枚举这个凸出来的矩形，设其为xxx。
在xxx下面的尽量往右伸，在xxx上面的往左伸。右伸是为了使得答案尽量大，左伸是为了让答案尽量大的时候可以保持平衡。
现在我们需要让xxx以及它上面的矩形可以立足于x−1x-1x−1的矩形上。
由于xxx要尽量往右，那我们就钦定这一大块的重心在rx−1r_{x-1}rx−1处（rir_iri表示iii矩形的右边横坐标）
又由于xxx上面的矩形要往左，所以我们就钦定它们的重心在rx−2r_x-2rx−2上（一定有满足这种条件的方案）。
设MMM为xxx上面的矩形的质量和，mxm_xmx为xxx的质量，依照公式：
rx−1=M(rx−2)+mx(rx−1)M+mxr_{x-1}=\frac{M(r_x-2)+m_x(r_x-1)}{M+m_x}rx−1=M+mxM(rx−2)+mx(rx−1)
如果我们知道rx−1r_{x-1}rx−1，就可以解出rxr_xrx，然后统计入答案。
那这个rx−1r_{x-1}rx−1是怎么来的呢？
显然不可以有上一次i=x−1i=x-1i=x−1时解出来的结果，具体原因不在赘述。
转化成另一个问题，现在xxx不是最右边的矩形，最右边的矩形会出现在它的上方。
所以xxx上面的矩形要尽量往右伸，我们可以将它们的重心钦定为rxr_xrx，然后方程就出来了。
rx−1=Mrx+m(rx−1)M+mzr_{x-1}=\frac{Mr_x+m(r_x-1)}{M+m_z}rx−1=M+mzMrx+m(rx−1)
同样可以通过rx−1r_{x-1}rx−1解出rxr_xrx，解出之后用来更新现在的rx−1r_{x-1}rx−1，计算下一个答案。
时间显然是线性的。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 300010
int n;
int w[N];
int main(){
scanf("%d",&n);
double sum=0;
for (int i=1;i<=n;++i)
scanf("%d",&w[i]),sum+=w[i];
sum-=w[1];
double r=0,ans=0;
for (int i=2;i<=n;++i){
sum-=w[i];
ans=max(r+1+sum/(sum+w[i]),ans);
r=r+w[i]/(sum+w[i]);
}
printf("%.8lf\n",ans);
return 0;
}
总结
在贪心的时候，有时可以“钦定”一下，假设除最好的情况来计算。