题目

• 原题地址：C. Balanced Stone Heaps
• 题目编号：1623C
• 目标算法：二分查找
• 难度评分：1600

1.题目大意

• n 堆石头
• 当前堆为 i （3 ≤ i ≤ n）， 共 h 个石头
• 可以移动 d 个石头到堆 i - 1 ，2·d 个石头到堆 i - 2 （0 ≤ 3·d ≤ h）。
• 当前堆的石头数为 0 是也算作一个堆。
• 求：移动石头后最大 · 石头数最少的堆 · 的石头数

2.题目分析

• 最大的最小值 ==> 二分。
• 根据给出的石头数范围，对其进行二分，选出符合题意的。
• 石头数小于 3 是不能移动的。
• 下面划掉的就不要看了
• ①
• 判断标准：对于设定的 mid，顺序遍历所有堆，判断每一堆的石头数是否大于等于 mid，如果小于就进行移动使其恰好等于mid。如果移动后所有堆都满足，则该 mid 成立。
• 注意：
  1. 由于当前堆必须同时给前两个堆补充，所以第一堆只能通过第三堆来补充。
  2. 最后两堆的石头不能通过后面的堆进行石头数的补充（因为后面没有）。
• ②
• 上面那个不大好，从前往后的时候要考虑两个堆对其进行补充，不如从后往前考虑，如下：
• 判断标准：对于设定的 mid，倒序顺序遍历所有堆，判断每一堆的石头数是否大于等于 mid，如果大于 mid 就把剩下多余的3的倍数的都分出去，如果小于mid就直接毙了。如果移动后所有堆都满足，则该 mid 成立。
• ③
• 麻了，又看错题了，题目要求必须按照从第 3 个到第 n 个的顺序来进行移动，也就是说，所有石头只能被移动 1 次，即不具有传递性，但是我们仍然可以倒着来，把原本属于他的那部分往前分就行了（不一定是原来就多出来的），即分出去多出来的属于原来的那部分。和之前相比也就是多建一个数组。

3.题目代码

#include <iostream>
#define MAX 1e9
using namespace std;

bool judge(int a[], int b[], int i, int mid)
{
    if(b[i]==mid)
        return true;
    else if(b[i]>=mid)
    {
        int d = min(a[i],b[i]-mid)/ 3;//分出去多出来的属于原来的那部分
        //b[i] -= 3*d;  //一遍过_没必要减了
        b[i-1] += d;
        b[i-2] += 2*d;
        return true;
    }
    else
        return false;
}

int main()
{
    int t;
    //freopen("./in.txt","r",stdin);
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int a[n];
        for(int i=0;i<n;i++)
            cin >> a[i];
        int l=1,r=MAX;
        int ans = 0;
        while(l<=r)
        {
            int mid = (l + r) / 2;
            int b[n];
            for(int j=0;j<n;j++)
                b[j] = a[j];
            bool flag = true;
            for(int i=n-1;i>=2;i--)
            {
                flag = judge(a, b, i , mid);
                if(!flag)
                    break;
            }
            if(flag&&b[0]>=mid&&b[1]>=mid)//单独判断头上两个_后面不行的表达式可以直接短路
                flag = true;
            else
                flag = false;
            if(flag)
            {
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        cout << ans << endl;
    }
    return 0;
}