建设悦生活网站,中国建筑装饰施工网,平面设计所需要的软件,我的企业邮箱在哪里看题干#xff1a;
给定N朵花的原先的高度#xff0c;从左到右排列#xff0c;最多浇水m天#xff0c;每天只能浇一次#xff0c;每次使得连续的w朵花的高度增长1#xff0c;问最后最矮的花的高度最高是多少。
Examples
Input
6 2 3
2 2 2 2 1 1Output
2Input
2 5 1
…题干
给定N朵花的原先的高度从左到右排列最多浇水m天每天只能浇一次每次使得连续的w朵花的高度增长1问最后最矮的花的高度最高是多少。
Examples
Input
6 2 3
2 2 2 2 1 1Output
2Input
2 5 1
5 8Output
9Note
In the first sample beaver can water the last 3 flowers at the first day. On the next day he may not to water flowers at all. In the end he will get the following heights: [2, 2, 2, 3, 2, 2]. The smallest flower has height equal to 2. Its impossible to get height 3 in this test.
解题报告 直接二分即可。树状数组差分维护区间更新复杂度O(nlognlogn)其实可以优化到nlogn直接用一个变量维护增量即可。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 4e5 5;
ll n,m,w,a[MAX];
ll c[MAX];
int lowbit(int x) {return x-x;}
ll sum(int x) {ll res 0;while(x) {res c[x];x - lowbit(x);} return res;
}
void update(int x,ll val) {while(x MAX) {c[x] val;x lowbit(x);}
}
bool ok(ll x) {ll cnt 0,tmp;for(int i 1; inw1; i) c[i]0;for(int i 1; in; i) {tmp sum(i);if(a[i] tmp x) {cnt (x-a[i]-tmp);update(i,x-a[i]-tmp);update(iw,-(x-a[i]-tmp));}} return cnt m;
}
int main()
{cinnmw; for(int i 1; in; i) scanf(%lld,ai);ll l 0,r 2e9,mid,ans;while(lr) {mid (lr)1;if(ok(mid)) l mid1,ans mid;else r mid-1;}printf(%lld\n,ans);return 0 ;
}
