CF1623C Balanced Stone Heaps

传送门

一句话题意

有若干堆石头排成一列，从第 $3$ 堆开始直至第 $n$ 堆依次执行如下操作：

假设当前位于第 $i$ 堆石头
任意选取一个 $d$ ，从第 $i$ 堆中取出 $3d$ 个石头，将其中 $d$ 个放到第 $i-1$ 堆， $2d$ 个放到第 $i-2$ 堆中

经过若干次上述操作后，最大化所有石堆中数量最少的那一堆的石头数，输出这个数

$n\le 2\times 10^5$

石堆大小 $h_i\le 10^9$

解法(TLDR)

考虑二分答案。对于一个确定的答案 $x$ ，从右向左考虑每次操作。对每堆石子，记录有多少石子是原有的，多少石子是移动过来的。从当前石堆中取石子时，要求移走的数量不能多于原有石子数量，也不能多于现有石子数量与答案之差。

一旦发现某堆石子现有数量不多于 $x$ ，则答案不可行，取左半边区间，否则取右半边区间

思路

最大化最小值是典型的二分答案 $x$ ，现在需要考虑如何用 $O(n)$ 左右的复杂度进行检验。

如果直接按照题目中所述的从左到右的顺序进行考虑，需要考虑的地方太多，例如对 $h_i$ 进行操作时可以使其大小暂时小于 $x$ ，因为它可以被之后的石堆补充； $h_{i-1}$ 可以被 $h_{i+1}$ 补充；甚至 $h_{i-2}$ 也可以被 $h_{i-1}$ 补充，不一而足。

所以干脆从右往左考虑

一开始读漏题了，直接从右往左一顿搞，再读题的时候直接就没想过这个方向_(:з」∠)_

从右往左考虑，只需贪心地看当前石堆有没有多余的石子，有的话就直接向左边堆。

但需要注意的是，由于原题是从左往右进行操作，意味着从当前石堆取石子的时候，取出的石子数量不能多于原有石子数量（因为此时还没有从右边石堆取石子对当前堆造成影响）。因而若我们从右往左考虑，需要分开处理当前石堆原有的石子数量，和来自其他石堆的石子数量。

这样就解决了，复杂度 $O(n\log n)$

Code

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=200000+100;
int T;
int n;
int h[maxn];

bool Check(int x)
{
    int th[maxn],neg[maxn];
    memset(neg,0,sizeof(int)*(n+1));
    memcpy(th,h,sizeof(int)*(n+1));
    for(int i=n;i>=3;--i)
    {
        if(neg[i]+th[i]<x)
            return false;
        else
        {
            int d=min(th[i]/3,(neg[i]+th[i]-x)/3);
            neg[i-1]+=d;
            neg[i-2]+=d*2;
        }   
    }
    if(neg[2]+th[2]<x || neg[1]+th[1]<x)
        return false;
    return true;
}

void Work()
{
    read(n);
    int l=0,r=0;
    for(int i=1;i<=n;++i)
        read(h[i]),r=max(r,h[i]);
    int ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(Check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    printf("%d\n",ans);
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}