CF1795C Tea Tasting

题意

有 \(n\) 个人和 \(n\) 杯茶，第 \(i\) 个人每次会喝 \(b_i\) 毫升的茶。第 \(i\) 杯茶有 \(a_i\) 毫升。总共会喝 \(n\) 轮茶，第 \(j\) 轮第 \(i\) 个人会尝试喝第 \(i+1-j\) 杯茶。喝的量为 \(\min(a_{i+1-j},b_i)\) 毫升，并且使 \(a_{i+1-j}\) 减少 \(\min(a_{i+1-j},b_i)\) 。问 \(n\) 轮后每个人喝了多少毫升茶。

其中，如果\(i+1-j\leq 0\)，那么第\(i\)个人停止品茶

思路

首先，每一个人能够喝到的茶都可以被表示为\(f_i\times b_i + ex_i\)，其中\(f_i\)表示这个人完整和了一整杯茶的数量，\(ex_i\)则表示这个人遇到的不满的茶对其做的贡献

可以发现，每个茶\(a_i\)只能对\(j\geq i\)的\(b_j\)造成影响，而他能做的完整的贡献（即，对应轮数喝了\(a_i\)）最大就是最大的\(k\)使得\(s_k-s_{i-1}\leq a_i\)，令\(s\)为\(b\)数组的前缀和

所以，可以先求出\(s\)，在对每一个\(a_i\)进行二分，找到最后一个能够进行完整贡献的数，并求出对应的\(f\)和\(ex\)即可，其中\(f\)可以用差分从\(O(n^2)\)优化到\(O(n)\)

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Maxn=2e5+10;
int n;
ll a[Maxn],b[Maxn];
ll s[Maxn],f[Maxn],ex[Maxn];
void run()
{
	cin>>n;
	memset(f,0,sizeof(f));
	memset(ex,0,sizeof(f));
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i];
	for(int i=1;i<=n;i++)
	{
		if(s[n]-s[i-1]<=a[i])
		{
			f[i]++;
			continue;
		}
		int l=i,r=n,mid,ans;
		while(l<r)
		{
			mid=l+r>>1;
			if(s[mid]-s[i-1]<=a[i]) l=mid+1;
			else r=mid;
		}
		ans=l-1;
		f[i]++; f[ans+1]--;
		ex[ans+1]+=a[i]-(s[ans]-s[i-1]);
	}
	for(int i=1;i<=n;i++) f[i]+=f[i-1];
	for(int i=1;i<=n;i++) cout<<f[i]*b[i]+ex[i]<<" ";
	cout<<endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--) run();
	system("pause");
	return 0;
}