关于二分
  • 板块学术版
  • 楼主LEE114514
  • 当前回复13
  • 已保存回复13
  • 发布时间2024/7/11 07:54
  • 上次更新2024/7/11 09:42:51
查看原帖
关于二分
750579
LEE114514楼主2024/7/11 07:54

需要在一个凸包 SS 上二分出第一个位置 xx,使得 Slope(Sx−1,Sx)>=kSlope(S_{x-1},S_x) >= k。

正确写法:

int query(double k){
	int l=1,r=top;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(K(sta[mid-1],sta[mid])>=k) l=mid;
		else r=mid-1;
	}
	return sta[l];
}

错误写法:

int query(double k){
	int l=1,r=top;
	while(l<=r){
		int mid=(l+r)>>1;
		if(K(sta[mid-1],sta[mid])>=k) l=mid+1;
		else r=mid-1;
	}
	return sta[r];
}

求指正。

2024/7/11 07:54
加载中...