当前快看：Educational Codeforces Round 143 (Rated for Div. 2) C(二分+差分维护)

2023-02-19 21:13:05 来源：博客园

(资料图片)

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个人都喝一口。

代码实现：

# includeusing 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 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>tt;while(tt--){solve();}}

关键词：小于等于是固定的第三个人