【每日一题】9月15日题目精讲(二分+差分数组）

二分答案，设当前答案为x，也就是碉值最低的话的碉值最大值为x。
从头到尾观察花，若a[i]<x，则对a[i]开头的w盆花怒浇(x-a[i])天，让其碉值达到x。让所有的a[i]都>=x。若怒浇的天数和小于等于m，则可行。可以用差分队列实现
因为差分数列b[i]=a[i]-a[i-1]，则当前点的值为sign，下一个点的值就为sign+b[i+1]。差分数列的L到R全加x操作： b[L]+=x; b[R+1]-=x;

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
//#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e7 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
///////////////////////////////////////////////////////////
int n, m, w;
int a[N], b[N];
void chafen(int l, int r, int x) {
    b[l] += x;
    if (r + 1 < n) {
        b[r + 1] -= x;
    }
}
bool solve(int mid) {
    for (int i = 1; i < n; i++)
        b[i] = a[i] - a[i - 1];//定义差分数组
    int sign = a[0];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (sign < mid) {
            chafen(i, i + w - 1, mid - sign);
            ans += mid - sign;//一次只能加1，所以差了多少就得加上多少次1，相当于加了mid-sign遍
            if (ans > m)//不符合要求了
                break;
            sign = mid;
        }
        sign += b[i + 1];
    }
    if (ans > m)
        return false;
    else
        return true;
}
int main()
{
    cin >> n >> m >> w;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int minn = INF;
    for (int i = 0; i < n; i++)
        minn = min(minn, a[i]);
    int l, r, mid;
    l = minn, r = minn + m;
    while (l <= r) {
        mid = (r + l) / 2 ;
        if (solve(mid))
            l = mid + 1;
        else
            r = mid-1;
    }
    cout << r << endl;
    return 0;
}