题目描述
有 n 堆石头，第 i 堆石头有 h i个。你可以按照如下规则进行操作：
从 i=3 到 i=n 按顺序操作：
由你选择一个非负整数 d，需满足3×d≤hi，令 hi−1加 d，令 hi−2加 2×d，令 hi减 3×d。
移动之后石堆可以为空。求操作之后最少的一堆石堆最大可以是多少。
输入格式
第一行一个整数 T，表示数据组数，
每组数据第一行一个整数 n，
第二行 n 个整数 h1到hn。
输出格式
每组数据输出一行，代表答案。
样例输入
4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6
样例输出
7
1
1
3
数据规模
1≤T≤2×105，3≤n≤2×105，1≤hi≤10 9，∑n≤2×105。
算法：二分答案，贪心。
思路：二分最小石堆的最大值，检查是否可以通过操作使最小石堆个数不小于mid。
check函数：每次操作只会使选定石堆减少，并令前面的石堆增加。所以只要从后往前遍历石堆，并对每个石堆操作，d是石堆保持在mid以上可取的最大值，这样所有没遍历的石堆个数都是满足已遍历石堆合法的情况下最大，如果遍历到某个石堆时该石堆石头个数小于mid，就能直接返回false。
int n;
int a[N],h[N];bool check(int mid)
{for(int i=1;i<=n;i++)h[i]=a[i];
for(int i=n;i>2;i–)
{if(h[i]<mid)return 0; int t=min(a[i],h[i]-mid)/3; h[i-1]+=t; h[i-2]+=2*t;} return h[1]>=mid && h[2]>=mid;}
void solve()
{int mid,ans=-1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } int l=0,r=*(max_element(a+1,a+n+1)); while(l<r) { mid=l+(r-l+1)/2; if(check(mid))l=mid; else r=mid-1; } cout<<l<<'\n';}