codeforces 460 C Present二分+貪欲最大化最小値問題

リンク:http://codeforces.com/problemset/problem/460/C 标题:n個の木を与え、m天を与え、長さw.m日間の水やりが可能で、毎日の水やりで長さwの連続するこの部分の木を1つ高くすることができます.水やりを要求した後、これらの木の最小値は最大いくらですか.
考え方:典型的な最大化最小値問題.この最小値を二分で検索し、この値が最小値になるかどうかを判断し、lowを更新してこの最小値を大きくすることができれば、だめならhighを更新します.判断するときに、木の高さを変えるには、この序列を巡って、木の高さがこの最小値より小さいときに水をやり、この木を起点とする長さwの木に水をやります.このような複雑さはO(n 2)であり,Tになる.
更新の複雑さを低減する:現在この木にどれだけ水が注がれているかを1つのマークcで記録することが考えられ、この木の高さに注がれている水が現在の最小値に達しているかどうかを判断するたびに、達していない場合は水を注水し、このマークに必要な水を加えるには、1つの配列b[]を用いて水を注水する場合を記録する必要がある.各灌水区間の突き当たりにある次の木について、灌水の影響を除去し、すなわち必要な灌水日数b[i]-=pを減らすと、各木に対してc+=b[i]を更新してどのくらい水をかけたかがわかる.水がかけられたことを記録し、水が与えられた区間外で除去される前に水が与えられた影響を記録する.更新操作を低減し,複雑度をO(n)に低減した.
まとめ:この方法はとても良くて、合宿の期間にも何度か会ったことがあるような気がします.勉強しなければなりません.区間のセグメント更新に活用できます.もちろんこの問題は線分木を用いて行うこともでき,区間最小値を記録し,怠惰な操作を用いて行うことができる.複雑度はO(n∗logn)である.しかし、この方法は明らかに書くのが便利で、もっと速くなります~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 100009
#define INF 0x3f3f3f3f
int n,m,w;
int a[M];
int b[M]; //    
int c;
bool judge(int x)
{
    int k = m;
    int c = 0;
    memset(b,0,sizeof(b));
    for(int i = 0;i < n;i++)
    {
        c += b[i];
        if(x > a[i]+c) //         
        {
            int p = x -a[i]-c; //     
            if(p > k) return false; //           
            k -= p;
            c += p;
            int minn = min(i+w,n);
            b[minn] -= p; //     w  ，       
        }
    }
    return true;
}
int main()
{
    while(scanf("%d %d %d",&n,&m,&w)==3)
    {
        int low = INF;
        int high = -INF;
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&a[i]);
            low = min(low,a[i]-1); //    -1
            high = max(high,a[i]+1); //    +1       -  <=1       
        }
        high += m;
        int mid;
        while(high - low > 1) //      
        {
            mid = (low+high)/2;
            if(judge(mid)) low = mid;
            else high = mid;
        }
        printf("%d
",low);
    }
    return 0;
}