Codeforces460C【二分+线段树】

69 阅读 0 评论 46 点赞

我是靠谱客的博主含糊皮卡丘，最近开发中收集的这篇文章主要介绍Codeforces460C【二分+线段树】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二分最小值，如果你能实现这个最小值是可以实现的，那么一定是最优的，因为每次区间+1，原来存在的最小值的个数还是存在的，但是新的可能会多起来，所以最小值递增还是最优到最优的；考虑如果不能实现这个最小值，那么他一定是比之前这个值少的，因为最小值不变，而且个数变少；区间维护可以线段树。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=1e5+10;
struct SegT{
    int sum;
    int val;
    int left;
    int right;
};

SegT q[N*4];
char id[N];
int n,m,w;
int a[N];

void Build(int num,int L ,int R)
{
    q[num].left=L;
    q[num].right=R;
    q[num].val=0;
    if(L==R)
    {
        q[num].sum=a[L];
        return;
    }
    int mid=(L+R)>>1;
    Build(2*num,L,mid);
    Build(2*num+1,mid+1,R);
    q[num].sum=q[2*num].sum+q[2*num+1].sum;
}

void PushDown(int num)
{
    if(q[num].val)
    {
        q[2*num].sum+=(q[2*num].right - q[2*num].left+1)*q[num].val;
        q[2*num].val+=q[num].val;
        q[2*num+1].sum+=(q[2*num+1].right - q[2*num+1].left+1)*q[num].val;
        q[2*num+1].val+=q[num].val;
        q[num].val=0;
    }
}

void Update(int num,int s,int t,int v)
{
    if(q[num].left>=s&&q[num].right<=t)
    {
        q[num].sum+=(q[num].right - q[num].left+1)*v;
        q[num].val+=v;
        return;
    }
    PushDown(num);
    int mid=(q[num].left+q[num].right)>>1;
    if(mid>=t)
        Update(2*num,s,t,v);
    else if(mid<s)
        Update(2*num+1,s,t,v);
    else
    {
        Update(2*num,s,mid,v);
        Update(2*num+1,mid+1,t,v);
    }
    q[num].sum=q[2*num].sum+q[2*num+1].sum;
}

int query(int num,int x)
{
    if(q[num].left==q[num].right&&q[num].left==x)
        return q[num].sum;
    PushDown(num);

    int mid=(q[num].left+q[num].right)>>1;

    if(mid>=x)
        return query(2*num,x);
    else
        return query(2*num+1,x);
}

bool Judge(int k)
{
    int ti=0;
    int tmp,x;
    Build(1,1,n);
    for(int i=n;i>=1;i--)
    {
        tmp=query(1,i);
        if(tmp>=k) continue;
        x=k-tmp;
        if(i>=w)
        {
            Update(1,i-w+1,i,x);
            ti+=x;
        }
        else
        {
            Update(1,1,i,x);
            ti+=x;
        }
        if(ti>m) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d%d",&n,&m,&w);
    int tmax=1,tmin=2e9;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmax=max(tmax,a[i]);
        tmin=min(tmin,a[i]);
    }
    int Left=tmin,Right=tmax+m;
    while(Left<Right)
    {
        int mid=Left+(Right-Left+1)/2;
        if(Judge(mid))
            Left=mid;
        else
            Right=mid-1;
    }
    printf("%dn",Left);
    return 0;
}