题目描述

难度分:$1500$

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

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

有$n$杯茶，第$i$杯有$a[i]$毫升。有$n$位品茶师，第$i$位一次可以喝$b[i]$毫升茶。下标从$1$开始。

品茶流程有$n$轮。

• 第一轮，第$i$位品茶师喝第$i$杯茶。$i \geq 1$。
• 第二轮，第$i$位品茶师喝第$i-1$杯茶。$i \geq 2$。第$1$位品茶师什么也不做。
• 第三轮，第$i$位品茶师喝第$i-2$杯茶。$i \geq 3$。第$1,2$位品茶师什么也不做。

依此类推。

输出每位品茶师喝茶的总量。

输入样例

4
3
10 20 15
9 8 6
1
5
7
4
13 8 5 4
3 4 2 1
3
1000000000 1000000000 1000000000
1 1 1000000000

输出样例

9 9 12 
5 
3 8 6 4 
1 2 2999999997 

算法

前缀和+差分+二分

直接模拟的时间复杂度是$O(n^2)$的，因此我们要换个角度来思考，考虑每一杯茶会被哪些品茶师品到？根据题面的操作，第$i$杯茶按照流程会被$[i,n]$的品茶师品到，但是有可能品到$j \in [i,n)$第$j$位品茶师时第$i$杯茶就已经消耗殆尽了。所以第一步我们要确定第$i$杯茶可以被哪些品茶师品到，对$b$求一个前缀和数组$s$，二分找到最远的$j$，满足$s[j]-s[i-1] \geq a[i]$。

这时候分为两种情况：

1. 如果$s[j]-s[i-1] \gt a[i]$，那么第$j$位品茶师就不能完整地喝$b[j]$毫升的茶，他只能喝$a[i]-(s[j-1]-s[i-1])$毫升，把这个体积累加到答案数组的$ans[j]$元素上。而中间$[i,j)$的品茶师都能发挥出全部的吞吐能力，构建一个差分数组$cnt$，操作差分数组$i$、$j$两个元素来表征区间加$1$。
2. 否则直接操作差分数组$i$、$j$另两个元素，$[i,j]$的所有品茶师都能发挥出全部实力。

对差分数组$cnt$求前缀和，$cnt[i]$就表示第$i$位品茶师完整地品了多少次茶，$ans[i]+cnt[i] \times b[i]$就是他品茶的容量。

复杂度分析

时间复杂度

对每个$i \in [1,n]$，都需要$O(log_2n)$的时间复杂度来二分出哪些品茶师能够品到第$i$杯茶，并$O(1)$更新差分数组和答案数组，时间复杂度为$O(nlog_2n)$。后续只需要$O(n)$遍历差分数组$cnt$计算出前缀和，每个$cnt[i]$与$ans[i]$综合一下就可以求得答案。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间消耗主要是三个线性空间的数组，$b$的前缀和数组$s$，记录每位品茶师的完整品茶次数的差分数组$cnt$。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, a[N], b[N];
LL s[N], cnt[N], ans[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        cnt[n + 1] = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            cnt[i] = ans[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
            s[i] = s[i - 1] + b[i];
        }
        for(int i = 1; i <= n; i++) {
            // 二分出第i杯茶会被哪些品茶师品
            int l = i, r = n;
            while(l < r) {
                int mid = l + r >> 1;
                if(s[mid] - s[i - 1] >= a[i]) {
                    r = mid;
                }else {
                    l = mid + 1;
                }
            }
            if(s[r] - s[i - 1] > a[i]) {
                cnt[i]++, cnt[r]--;
                ans[r] += a[i] - (s[r - 1] - s[i - 1]);
            }else {
                cnt[i]++, cnt[r + 1]--;
            }
        }
        for(int i = 1; i <= n; i++) {
            cnt[i] += cnt[i - 1];
            ans[i] += cnt[i] * b[i];
            printf("%lld ", ans[i]);
        }
        puts("");
    }
    return 0;
}