是初值的问题吗 为什么wa了最后一个点。。。

回复帖子

@lele2002 2019-01-23 20:01 回复
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;
const int MN=505050;
struct No{
    int pos,fen;
}no[MN];
long long f[MN],spj;
int n,d,k;
deque <No> q;
void qpushb(int x)
{
    No bp;
    bp.pos=no[x].pos,bp.fen=f[x];
    while(!q.empty())
    {
        if(q.back().fen>=bp.fen)
            break;
        q.pop_back();
    }
    q.push_back(bp);
}

//qshidanjianduilie
bool ok(int agile)
{
//  cout<<agile<<':';
    while(!q.empty())
        q.pop_front();
    int minn=max(d-agile,1),zdz=d+agile;
//  cout<<minn<<' '<<zdz<<endl;
    f[0]=0;
    for(int i=1;i<=n+1;i++)
        f[i]=-101001011010101;
    q.push_front((No){0,0});
    int qe=0;
    for(int i=1;i<=n;i++)
        if(no[i].pos<=zdz&&no[i].pos>=minn)
        {
            qe=i;
            break;
        }
    int pl=1;
    if(!qe)
        return 0;
    for(int i=qe;i<=n;i++)
    {
        while(!q.empty()&&no[i].pos-q.front().pos>zdz)
            q.pop_front();
        while(no[i].pos-no[pl].pos>zdz)
            pl++;
        while(no[i].pos-no[pl].pos>=minn&&no[i].pos-no[pl].pos<=zdz)
            qpushb(pl),pl++;
        if(q.empty())
            continue;
        f[i]=q.front().fen+no[i].fen;
        if(f[i]>=k)
            return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>no[i].pos>>no[i].fen;
        if(no[i].fen>0)
            spj+=no[i].fen;
    }
    if(spj<k)
    {
        cout<<-1<<endl;
        return 0;
    }
    int l=0,r=1000000000,ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(ok(mid))
        {
//          cout<<1<<endl;
            ans=mid,r=mid-1;
        }
        else
        {
//          cout<<0<<endl;
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。