Present
来自
【每日一题】
609 浏览
0 回复
2020-09-20
Present
https://ac.nowcoder.com/acm/problem/110615
前言
刚开始什么思路都没有,但是突然想到了一道题——换教室,似乎也是二分,然后运用到这一道题,似乎就明了了
分析
这道题的话,通过二分最小的w,是每一盆花的a[i]>=w,并且浇的天数小于等于m。这就是主要思路。
实现
题目中给出了一个w(刚开始我也不知所措啊QwQ),然而我们想一想,设一个f[i]表示将[i,i+w-1]区间浇水的天
数,那么之后对于一个j,因为之前的第j-w盆肯定浇过,那么就可以减去那一盆的贡献,然后求出对于第j盆是否
还需要再浇。
代码
/*二分加差分*/
/*
每次二分一个最小值,算出使每一个a
都大于它至少要浇多少次,而之前(i-w)如果
有浇过,那么可以减去那一次的次数
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#define R register
#define ll long long
#define inf INT_MAX
using namespace std;
const int N=1e5+10;
ll n,m,w;
ll a[N],f[N];
bool check(ll k)
{
ll rem=m,us=0;
//还剩下的,已经用过的
for (int i=1;i<=n;i++)
{
if(i>=w) us-=f[i-w];
//说明之前这个区间浇过水了
f[i]=max((ll)0,k-us-a[i]);
us+=f[i];
rem-=f[i];
if(rem<0) return 0;
}
return 1;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&w);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll l=1,r=1e15,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}