Codeforces Round #262 (Div. 2) 题解 - c++编程基础

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

input

2 5 1
5 8

output

传送门：点击打开链接解题思路：对所求解的值进行二分。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; }

Codeforces Round #262 (Div. 2) 题解(二)