CF1623 C.Balanced Stone Heaps【二分】

题目链接：codeforces 1623C

题解

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

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}