#P3182. [Coci2012]BLOKOVI

    ID: 2358 传统题 1000ms 512MiB 尝试: 30 已通过: 9 难度: 6 上传者: 标签>难度分类提高动态规划线性 DP模拟与实现技巧坐标变换滚动数组CF2100

[Coci2012]BLOKOVI

[COCI 2011/2012 #5] BLOKOVI

题目描述

在平面直角坐标系中,从下至上放置 NN 个矩形。第 ii 个矩形的质量为 mim_i,各矩形的宽均为 22、高均为 hh。矩形的边平行于坐标轴,从低到高,其下边的纵坐标分别为 0,h,2h,3h,…,(N−1)h0,h,2h,3h,\ldots,(N-1)h。最下面的矩形左下角为 (−2,0)(-2,0),右下角与原点重合。

设第 ii 个矩形下边中点的横坐标为 xix_i。对于任意非空的矩形集合 SS,其质心的横坐标是这些矩形中心横坐标的质量加权平均值:

$$x_S=\frac{\sum_{i\in S}m_i x_i}{\sum_{i\in S}m_i}.$$

如果对每个上方还有矩形的矩形 ii,其上方所有矩形的质心横坐标与 xix_i 的距离都不超过 11,则排列是稳定的。也就是说,上方这些矩形的质心必须落在矩形 ii 所覆盖的横坐标范围内。

左图中的排列不稳定,因为最上方两个矩形的质心超出了紧挨着它们下方的矩形的横坐标范围。右图中的排列是稳定的。

给定各矩形的质量。在所有稳定排列中,求任一矩形的任一顶点所能达到的最大横坐标。矩形自下向上的顺序固定。

输入格式

第一行包含正整数 NN(2≤N≤3×1052\le N\le 3\times 10^5)。

接下来 NN 行,从最下面的矩形到最上面的矩形,每行给出一个质量 mim_i(1≤mi<1041\le m_i<10^4)。

输出格式

输出一行一个实数,表示最大横坐标。答案与标准答案的绝对误差不得超过 10−610^{-6}。

2
1
1
1.000000
3
1
1
1
1.500000
3
1
1
9
1.900000

原题评分

占总分 30%30\% 的测试用例中,矩形质量按非增顺序给出。

原题面 PDF