C. Tea Tasting

https://codeforces.com/contest/1795/problem/C
用二分+前缀和+差分卡过
#include <iostream>

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=2e5+10;

int t;

int n;

long long a[N],b[N],s[N],res[N],num[N];

void fact(int x,int l,int r){

	num[l]++;

	int k=l-1;

	while(l<r){

		int mid=l+r>>1;

		if(s[mid]-s[k]<x) l=mid+1;

		else r=mid;

	}

	if(s[l]-s[k]<=x) num[l+1]--;

	else num[l]--,res[l]+=x-(s[l-1]-s[k]);//这里第l个人没有喝满

}

int main(){

	cin>>t;

	while(t--){

		cin>>n;

		memset(num,0,sizeof num);//注意归零

		memset(res,0,sizeof res);

		for(int i=1;i<=n;i++) cin>>a[i];

		for(int i=1;i<=n;i++){

			cin>>b[i];

			s[i]=s[i-1]+b[i];

		}

		for(int i=1;i<=n;i++){

			fact(a[i],i,n);

		}

		for(int i=1;i<=n;i++){

			num[i]+=num[i-1];

			res[i]+=num[i]*b[i];

			cout<<res[i]<<" ";

		}

		cout<<endl;

}

}

/*

题目大意就是给定n杯茶多少毫升和n个人能喝多少毫升，一开始第i个人在喝第i杯茶

每喝完一次，他们就要向前走去喝第i-1杯茶，喝完为止，第一个人往前走就直接去除

思路就是对于前缀和和差分和二分

对于第i杯茶，找到第i~j这段和恰好大于a[i],然后第i个人的喝茶数就加一

对于第j个人需要特判3种情况

只需二分查找和，并记录每个人的喝茶数量，以及加上喝了不到最大喝茶量的茶

就是答案

*/
巴特西

C. Tea Tasting

最新文章

热门文章
