题目描述

难度分:$1600$

输入$T(\leq 2 \times 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(3 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

有$n$堆石子，第$i$堆石子有$a[i]$颗。从左到右依次操作第$i=3,4,5,…,n$堆石子。

每次操作，你从第$i$堆中拿出$3k$颗石子，其中$k$颗放入第$i-1$堆，另外$2k$颗放入第$i-2$堆。

输出$min(a)$最大可以是多少。

输入样例

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

算法

二分答案

看到求最小值的最大值，就可以想到用二分答案来做。对于某个要达到的最小值$limit$，分为以下两种情况：

1. 如果能做到最小值$\geq limit$，就记录答案并往右搜索看能不能更大。
2. 否则这个限制就太严格了，应该往左搜索。

关键在于如何$check$，注意到只有$a[1]$和$a[2]$是没有操作空间的，因此我们可以从后往前贪心。对于满足$a[i] \geq limit$的$i$，将它多出的部分往前面“匀”，即$d=\lfloor \frac{a[i]-limit}{3} \rfloor$（其中$\lfloor . \rfloor$表示对$.$向下取整）。但由于真正操作的时候还是按照从前往后的顺序，所以匀出去的那一部分不能超过原始$a[i]$的极限，两者计算出来的$d$要取$min$。

复杂度

时间复杂度

二分的时间复杂度为$O(log_2A)$（其中$A$是二分时上下界的距离），$check$的时间复杂度为$O(n)$，因此整个算法的时间复杂度为$O(nlog_2A)$。

空间复杂度

每次$check$的时候需要对原数组拷贝出来一个副本进行操作，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, h[N];
LL s[N];

bool check(LL limit) {
    for(int i = 1; i <= n; i++) {
        s[i] = h[i];
    }
    for(int i = n; i >= 3; i--) {
        if(s[i] >= limit) {
            LL d = min(s[i] - limit, (LL)h[i]) / 3;
            s[i] -= 3*d;
            s[i - 1] += d;
            s[i - 2] += 2*d;
        }else {
            return false;
        }
    }
    return s[1] >= limit && s[2] >= limit;
}

void solve() {
    LL l = 0, r = 2e14;
    while(l < r) {
        LL mid = l + r + 1 >> 1;
        if(check(mid)) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    printf("%lld\n", r);
}

int main() {
    scanf("%d", &t);
    for(int index = 1; index <= t; index++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &h[i]);
        }
        solve();
    }
    return 0;
}