求助关于cdq里二分斜率的问题
查看原帖
求助关于cdq里二分斜率的问题
375953
Lgx_Q楼主2022/8/16 11:44

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

#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;
}
2022/8/16 11:44
加载中...