题目描述
难度分:1500
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105),长为n的数组a(1≤a[i]≤109),长为n的数组b(1≤b[i]≤109)。
有n杯茶,第i杯有a[i]毫升。有n位品茶师,第i位一次可以喝b[i]毫升茶。下标从1开始。
品茶流程有n轮。
- 第一轮,第i位品茶师喝第i杯茶。i≥1。
- 第二轮,第i位品茶师喝第i−1杯茶。i≥2。第1位品茶师什么也不做。
- 第三轮,第i位品茶师喝第i−2杯茶。i≥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(n2)的,因此我们要换个角度来思考,考虑每一杯茶会被哪些品茶师品到?根据题面的操作,第i杯茶按照流程会被[i,n]的品茶师品到,但是有可能品到j∈[i,n)第j位品茶师时第i杯茶就已经消耗殆尽了。所以第一步我们要确定第i杯茶可以被哪些品茶师品到,对b求一个前缀和数组s,二分找到最远的j,满足s[j]−s[i−1]≥a[i]。
这时候分为两种情况:
- 如果s[j]−s[i−1]>a[i],那么第j位品茶师就不能完整地喝b[j]毫升的茶,他只能喝a[i]−(s[j−1]−s[i−1])毫升,把这个体积累加到答案数组的ans[j]元素上。而中间[i,j)的品茶师都能发挥出全部的吞吐能力,构建一个差分数组cnt,操作差分数组i、j两个元素来表征区间加1。
- 否则直接操作差分数组i、j另两个元素,[i,j]的所有品茶师都能发挥出全部实力。
对差分数组cnt求前缀和,cnt[i]就表示第i位品茶师完整地品了多少次茶,ans[i]+cnt[i]×b[i]就是他品茶的容量。
复杂度分析
时间复杂度
对每个i∈[1,n],都需要O(log2n)的时间复杂度来二分出哪些品茶师能够品到第i杯茶,并O(1)更新差分数组和答案数组,时间复杂度为O(nlog2n)。后续只需要O(n)遍历差分数组cnt计算出前缀和,每个cnt[i]与ans[i]综合一下就可以求得答案。因此,整个算法的时间复杂度为O(nlog2n)。
空间复杂度
空间消耗主要是三个线性空间的数组,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;
}