flowers (he can do that only once at a day). At that each watered flower grows by one height unit on that day. The beaver wants the height of the smallest flower be as large as possible in the end. What maximum height of the smallest flower can he get? Input
The first line contains space-separated integers n, m and w (1?≤?w?≤?n?≤?105; 1?≤?m?≤?105). The second line contains space-separated integers a1,?a2,?...,?an (1?≤?ai?≤?109).
Output
Print a single integer ― the maximum final height of the smallest flower.
Sample test(s) input
6 2 3
2
2 2 2 1 1
output
2
input
2 5 1
5 8
output
9
传送门：点击打开链接 解题思路： 对所求解的值进行二分。ps：这里的b数组大小是n+w。 代码：
#include
#include
#include
#include
#include
using namespace std; typedef long long lint; typedef double DB; const int MAXN = 2e5+10; const int INF = 2e9; lint a[MAXN], b[MAXN], ans; int n, m, w; bool check(lint k) { memset(b, 0, sizeof(b)); lint sum = 0, d = 0; for(int i=1; i<=n; ++i) { sum += b[i]; lint tp = k - a[i] - sum; if(tp > 0) { sum += tp; b[i+w] -= tp; d += tp; // printf("%I64d %I64d\n", tp, d); if(d > m) return false; } } return true; } int main() { scanf("%d%d%d", &n, &m, &w); for(int i=1; i<=n; ++i) scanf("%I64d", a+i); lint l = 1, r = 1ll*INF; while(l <= r) { lint mid = (l+r)>>1; if(check(mid)) l = mid + 1, ans = mid; else r = mid - 1; // printf("%I64d %I64d\n", l, r); } printf("%I64d\n", ans); return 0; }