洛谷P4064 加法 [JXOI2017] 贪心

时间：2021-10-17 19:38:23

正解:贪心

解题报告:

传送门!

首先最小值最大显然考虑二分?然后就二分一个值mid,从左往右考虑,对于小于等于mid的点显然可以求出这个点至少要加几次,然后找到覆盖这个点的右端点max的区间区间加上它要加的数就好

然后具体的操作和短路那题差不多,,,同差分+开个数组+全局变量,over

挺显然的贪心?不解释了QAQ

那就等下直接放代码了QAQ

(我怎么觉得我题解越来越简洁了鸭嘻嘻

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+,inf=1e9;

int n,m,k,dat,a[N],b[N],c[N],l,r,ret;

vector<int>nod[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(ri gd,ri gs){return gd>gs;}

il bool check(ri x)

{

    priority_queue<int>Q;ri as=,tot=;

    rp(i,,n)b[i]=max(,(x-a[i]+dat-)/dat);memset(c,,sizeof(c));

    rp(i,,n)

    {

        tot+=c[i];ri sz=nod[i].size();rp(j,,sz-)Q.push(nod[i][j]);

        while(!Q.empty() && tot<b[i])

        {

            if(Q.top()<i)return false;++tot;--c[Q.top()+];Q.pop();++as;

        }

        if(tot<b[i] || as>k)return false;

    }

    return true;

}

int main()

{

    // freopen("4064.in","r",stdin);freopen("4064.out","w",stdout);

    int T=read();

    while(T--)

    {

        n=read();m=read();k=read();dat=read();ret=l=;rp(i,,n)a[i]=read(),nod[i].clear();r=inf;

        rp(i,,m){ri l=read();nod[l].push_back(read());}

        while(l<r){ri mid=(l+r)>>;if(check(mid+))l=mid+;else r=mid;}

        printf("%d\n",l);

    }

    return ;

}

然后放个代码吼qwq

最后写个小细节,,,虽然我觉得一般人都不会错只有我比较傻逼没注意QAQ

就是它check会有很多次嘛,所以用队列的时候记得每次先清空

当然也可以选择就不开全局的queue,在check函数中定义,这样每次拿到的就是个空的队列辣QwQ

over!

相关文章