Codeforces 460C —— Present（二分答案）

题目：Present

题意：给定N朵花的原先的高度，从左到右排列，最多浇水m天，每天只能浇一次，每次使得连续的w朵花的高度增长1，问最后最矮的花的高度最高是多少。

直接对答案进行二分，对于高度X的判定，从左往右遍历花的高度，如果当前高度低于X，则用相应的天数浇水，如果天数不够就说明不可行。

至于处理方面，目测写个线段树、树状数组维护区间问题应该也可以，但也有比较简便的方法。

用一个数组b，初始化全部为0，再用一个变量C，初值也为0，如果当前需要浇水p天，则C+=p，表明后面的花也会浇到，在b[i+w]的位置减去p，表示当前的浇水的影响到这里结束，每访问到一个位置就先用C+b[i]，然后再判断a[i]+C与x的大小关系。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, w;
int a[100010], b[100010];
bool ok(int x){
memset(b, 0, sizeof(b));
int k = m;
int c = 0;
int p;
for(int i=0; i<n; i++){
c += b[i];
if(a[i]+c<x){
p = x-a[i]-c;
if(p>k) return 0;//天数不足，不可行
k-=p;
c+=p;
b[(i+w)>=n?n:(i+w)]-=p;
}
}
return 1;
}
int main(){
while(~scanf("%d %d %d", &n, &m, &w)){
int low, top;
for(int i=0; i<n; i++){
scanf("%d", a+i);
if(i){
low = min(low, a[i]);
top = max(top, a[i]);
}
else{
low=top=a[i];
}
}
top+=m;
int ans = low;
while(low<=top){
int mid = (low+top)>>1;
if(ok(mid)){
ans = max(ans, mid);
low = mid+1;
}
else{
top = mid-1;
}
}
printf("%dn", ans);
}
return 0;
}

最后

以上就是碧蓝小土豆为你收集整理的Codeforces 460C —— Present（二分答案）的全部内容，希望文章能够帮你解决Codeforces 460C —— Present（二分答案）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。