Educational Codeforces Round 143 (Rated for Div. 2) C(二分+差分维护)
C.Tea Tasting
题目大意:
给定n杯茶,n个人,一个进行n论赏茶,赏茶的规律如下:
第1轮,第一个人喝第1杯茶,第二个人喝第二杯茶....第i个人喝第i杯茶
第2轮,第一个人结束赏茶,第二个人喝第一杯茶,第三个人喝第二杯茶...第i个人喝第i-1杯茶
.....
每杯茶的总量不一样,给定为a[i] ml
每个人每次喝的量是固定的为b[i] ml
问最终每个人喝到了多少毫升的茶?
解题思路:
我们观察到对于第i杯茶来说,总会被第i,i+1,i+2,i+3.....n个人喝到,所以我们考虑对于第i杯茶,它能够完全满足第(i ~ j)个人的喝茶需求,这个j我们可以通过二分得到(对b[i]做前缀和,考虑pre[mid]-pre[i-1]是否小于等于a[i]),所以第i~j个人的需求可以都喝一口第i杯茶,剩余的茶被第j+1个人喝,然后我们可以用差分来维护第i~j个人都喝一口。
代码实现:
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5+10,inf = 1e18,mod = 1e9+7;
int pre[N],c[N];
int ans[N];
void solve(){
int n;
cin>>n;
vector<int> a(n+1),b(n+1);
for(int i = 1;i <= n;++i) cin>>a[i];
for(int i =1;i <= n;++i){
cin>>b[i];
pre[i] = pre[i-1]+b[i];
ans[i] = c[i] = 0;
}
for(int i = 1;i <= n;++i){
int l = i-1,r = n;
int now = i-1;
while(l<=r){
int mid = (l+r)>>1;
if(pre[mid]-pre[i-1]<= a[i]){
l = mid+1;
now = mid;
}
else r = mid-1;
}
c[i]+=1;
c[now+1] -= 1;
if(now<n) ans[now+1]+=a[i]-(pre[now]-pre[i-1]);
}
for(int i = 1;i <= n;++i) c[i] += c[i-1];
for(int i = 1;i <= n;++i){
ans[i] += c[i]*b[i];
}
for(int i = 1;i <= n;++i){
cout<<ans[i]<<" \n"[i==n];
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt;
cin>>tt;
while(tt--){
solve();
}
}
标签:pre,二分,Educational,Rated,143,个人,int,Codeforces,差分
From: https://www.cnblogs.com/empty-y/p/17135602.html