题解 P4594 【[COCI2011-2012#5] BLOKOVI】

decoqwq · 2020-07-23 10:03:19 · 题解

考虑贪心，考虑每次从上往下加入一个块，新块 i 的贡献是 \frac{m_i}{\sum m}，代表新 x 重心的移动量，考虑贪心的选择向左或者向右，每次在原最右边 +\Delta 或者向左移动变为 2-\Delta，最后取最靠右的答案即可。

#include <bits/stdc++.h>
#define maxn 300010
using namespace std;
int n,a[maxn];
double sum,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=n;i>1;i--)
    {
        int qwq=a[i];
        a[i]+=a[i+1];
        double del=double(qwq)/double(a[i]);
        ans=max(ans,max(ans+del,2-del));
    }
    printf("%.8lf",ans);
}