codeforces1623C Balanced Stone Heaps（二分/贪心）

题目链接：codeforces 1623C

题目思路：

二分答案，对最小高度二分。

对于当前假设的高度 $x$，每次操作的时候，采取贪心策略，倒序枚举，把当前的石头数尽可能地放到前两堆。需要注意的是，当前堆石头数减少的数量一定是 $0$ 或是$3$ 的正整数倍数。

参考代码：

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n, mx;
ll a[N], b[N];
bool check(ll x) {
   
    for (int i = 1; i <= n; i++) b[i] = a[i];
    ll d;
    for (int i = n; i >= 3; i--) {
   
        if (b[i] < x) {
   
            return false;
        }
        d = (b[i] - x) / 3;
        d = min(d, a[i] / 3);
        b[i-1] += d, b[i-2] += 2*d;
    }
    return b[1] >= x && b[2] >= x;
}
void solver() {
   
    mx = -1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
   
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    ll l = 0, r = mx, mid;
    while (l < r) {
   
        mid = (l + r + 1) >> 1;
        if (check(mid)) {
   
            l = mid;
        } else {
   
           	r = mid - 1;
        }
    }
    cout << l << endl;
}
int main() {
   
    int _ = 1;
    cin >> _;
    while (_--) {
   
        solver();
    }
    return 0;
}