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 ??? 那我就不知道了。