本文主要是介绍Codeforces Round #262 (Div. 2) C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C. Present
题意：n朵花，有各自的高度，有m天时间，每天能给连续的w朵花浇水，浇水后长高1。问m天后高度最低的花的最大值。
思路：二分答案，贪心浇水判断。这题比赛的时候我一点想法都没有，dp不行，线段树不会写。。赛后看了别人的解法才知道怎么做。。二分的之后上限和下限就去可能的上下限，要注意二分终止的条件，判断的时候如果发现不满足指定高度的花，就从左往右浇水，注意判断的复杂度是O(n)，如果写成O(n*w)会超时，方法是用一个数组来累积浇不到水的天数，详细见代码。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 1000000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))using namespace std;int h[100010];
int tmp[100010];
int n,m,w;bool judge(int k){memset(tmp,0,sizeof(tmp));int mm=m;for(int i=1;i<=n;i++){tmp[i]+=tmp[i-1];int d=k-h[i]+tmp[i];if(d>0){mm-=d;if(mm<0)return false;k-=d;if(i+w<=n){tmp[i+w]+=d;}}}return true;
}int main(){while(cin>>n>>m>>w){int _min=INF;for(int i=1;i<=n;i++){cin>>h[i];_min=min(_min,h[i]);}int l=_min;int r=_min+m;int mid;do{int mm=m;mid=(l+r+1)/2;if(judge(mid)){l=mid;}else{r=min(mid,r-1);}}while(l!=r);cout<<l<<endl;}return 0;
}
这篇关于Codeforces Round #262 (Div. 2) C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
