求助关于cdq里二分斜率的问题

P4655 [CEOI2017] Building Bridges

Lgx_Q @ 2022-08-16 11:44:55

为什么这里二分斜率会错,检查了很多遍了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000010;
int n,f[maxn],len,q[maxn];
struct zz
{
    int h,w,id,g;
    double x,y;
}a[maxn];
bool cmp(zz a,zz b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
double slope(zz a,zz b)
{
    if(a.x==b.x)return 0x3f3f3f3f3f3f3f3f;
    return (a.y-b.y)/(a.x-b.x);
}
int erfind(double k)
{
    int lo=1,hi=len;
    while(lo<=hi)
    {
        int mid=lo+hi>>1;
        bool s=false,t=false;
        if(mid==1||slope(a[q[mid]],a[q[mid-1]])<=k)
        {
            s=true;
        }
        if(mid==len||slope(a[q[mid+1]],a[q[mid]])>=k)
        {
            t=true;
        }
        if(s&&t)return mid;
        else if(s)
        {
            lo=mid+1;
        }
        else
        {
            hi=mid-1;
        }
    }
}
void cdq(int l,int r)
{
    if(l==r)
    {
        a[l].x=a[l].h;
        a[l].y=f[a[l].id]-a[l].w+a[l].h*a[l].h;
        return;
    }
    int mid=l+r>>1;
    cdq(l,mid);
    sort(a+l,a+1+mid,cmp);
    len=0;
    for(int i=l;i<=mid;i++)
    {
        if(len>1&&slope(a[q[len]],a[q[len-1]])>=slope(a[i],a[q[len]]))
        {
            len--;
        }
        q[++len]=i;
    }
    for(int i=mid+1;i<=r;i++)
    {
        int j=q[erfind(2*a[i].h)];
        f[a[i].id]=min(f[a[i].id],f[a[j].id]+a[i].g-a[j].w+(a[i].h-a[j].h)*(a[i].h-a[j].h));
    }
    cdq(mid+1,r);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].h);
        a[i].id=i;
    }
    memset(f,0x3f,sizeof f);
    f[1]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].w);
        a[i].w+=a[i-1].w;
        a[i].g=a[i-1].w;
    }
    cdq(1,n);
    return 0;
}

by JackMerryYoung @ 2022-08-16 12:13:02

@Sktn0089 你右边还没做完呢哪来的单调性???


by Lgx_Q @ 2022-08-16 12:24:36

右边不是在左边二分斜率吗


by Lgx_Q @ 2022-08-16 12:27:44

@JackMerryYoung 我不是排序,我是直接在左边二分


by JackMerryYoung @ 2022-08-16 12:40:02

@Sktn0089 ??? 那我就不知道了。


|