我是靠谱客的博主 专一奇迹,这篇文章主要介绍Codeforces 460C Present 二分+前缀和,现在分享给大家,希望可以做个参考。

点击打开链接

题意:n个数,m次操作 n,m<=1e5,操作:每次将[i,i+w)中的数+1,问m次操作后最小值最大为?
二分最值x,判定:res为a[i]过去被累加次数,显然res=[a[i-w+1]~a[i-1]]被累加的次数之和,利用前缀和b[i]记录前i个数累加之和即可求出res 
若a[i]+res<x 则a[i]肯定要操作,更新次数即可. 

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; ll n,m,w,a[N]; ll b[N];//前i个数总共被加多少次 bool check(ll x) { ll cnt=0; memset(b,0,sizeof(b)); for(ll i=1;i<=n;i++) { ll res=0; b[i]=b[i-1];// ll k=max((ll)0,i-w);// res=b[i-1]-b[k];//a[i]过去被加了多少次? [i-w+1~i-1]加了多少次 if(a[i]+res<x) b[i]+=x-(a[i]+res); } return b[n]<=m; } int main() { while(cin>>n>>m>>w) { for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); ll l=1,r=2e10,ans; while(l<=r) { ll mid=(l+r)>>1; if(check(mid)) { ans=mid; l=mid+1; } else r=mid-1; } cout<<ans<<endl; } return 0; }


最后

以上就是专一奇迹最近收集整理的关于Codeforces 460C Present 二分+前缀和的全部内容,更多相关Codeforces内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(64)

评论列表共有 0 条评论

立即
投稿
返回
顶部