P4594 [COCI2011-2012#5] BLOKOVI解题报告

解题报告

---

P4594 [COCI2011-2012#5] BLOKOVI解题报告：

更好的阅读体验

题意

从下到上有$n$个矩形，重量分别为$m_{1\cdots n}$，以最下面矩形右下角为原点建立坐标系，那么定义一个矩形的重心$c(i)$为过其几何重心平行于$y$轴的直线，一个矩形前缀的重心为直线$x=\frac{\sum(m_i\cdot c(i))}{\sum m_i}$。

定义一种摆放方式合法当且仅当任意矩形的重心与其上方的矩形前缀的重心水平距离不超过$1$，求出矩形右端点$x$值最大值能取到的最大值。

$1\leqslant n\leqslant 3\times 10^5$。

分析

神仙题。

从下到上一个个考虑显然会产生后效性，因此从上到下讨论。

设现在到了第$i$个矩形，之前的矩形（不包括$i$）重量和为$tot$，之前的矩形的重心与当前矩形左端点的水平距离为$dis$（这是需要决策的值），前$i-1$个矩形右端点与它们的重心距离最大值为$d$。

容易知道新的重心与左端点的距离为$\frac{tot\cdot dis+m_i\cdot 1}{m_i+tot}$，前$i$个矩形右端点与左端点的距离最大值为$\max\{2,dis+d\}$

因此可以知道前$i$个矩形右端点与重心距离的最大值为

$$\max\{2,dis+d\}-\frac{tot\cdot dis+m_i}{m_i+tot}=\frac{\max\{2(m_i+tot),(dis+d)(m_i+tot)\}-tot\cdot dis-m_i}{m_i+tot}\\=\frac{\max\{(2-dis)\cdot tot+m_i,(dis-1)\cdot m_i+(m_i+tot)\cdot d\}}{m_i+tot}$$

易知$\max$左边的是随$dis$增加单调减少的，$\max$右边的是随$dis$增加单调增加的，因此在允许的情况下，$dis$会尽可能取大或取小。

可以计算出矩形$i$为底部时上一个的矩形的左端与当前矩形的左端水平距离最大值为$\frac{m_i}{tot}$，那么在右边放可以让当前的答案增加这个值。

如果放在右边，那么我们考虑两个矩形夹住当前矩形，那么至少要夹住$\frac{m_i}{tot}$长度的矩形才能保证平衡，那么当前右端为$2-\frac{m_i}{tot}$。

这样贪心下去就好了，时间复杂度：$O(n)$。

但是到这里其实我还是有一点疑惑，希望以后这道题的贪心有更好的解释。

代码

#include<stdio.h>
const int maxn=300005;
int n;
long long tot;
double ans;
int m[maxn];
inline double max(double a,double b){
    return a>b? a:b;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&m[i]);
    for(int i=n;i>1;i--)
        ans=max(ans,max(ans+1.0*m[i]/(m[i]+tot),2.0-1.0*m[i]/(m[i]+tot))),tot+=m[i];
    printf("%.8lf\n",ans);
    return 0;
}