一些三分的模板见解

三分的话就是二分多了一点变化，首先要保证三分的东西是具有凸函数性质的，就像二分的东西具有单调性一样.
然后就是整数和浮点了，这里的话板子上是有一些区别的，浮点的话用eps去比，整数缩两边的边界
浮点板子

#include <bits/stdc++.h>
using namespace std;
double a[100005];
int n;
double f(double x)
{
	double ans=0;
	double re=x;
	for(int i=n;i;i--)
	ans+=x*a[i],x*=re;
	ans+=a[n+1];
	return ans;
}
int main()
{
	double l,r,eps=1e-5;
	cin>>n>>l>>r;
	for(int i=1;i<=n+1;i++) cin>>a[i];
	for(int i=1;i<=100;i++)
	{
		double mid=(l+r)/2.0;
		if(f(mid+eps)>f(mid-eps)) l=mid;
		else r=mid;
	}
	printf("%.5f",l);
}

整数板子

#include <bits/stdc++.h>
using namespace std;
long long a[1000005],k,ans=LLONG_MAX;
long long n;
long long f(long long x)
{
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=llabs(x-a[i]),x+=k;
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	long long l=-1000000000000L,r=1000000000000L;
	for(int i=0;i<100;i++)
	{
		long long len=r-l;
		if(f(l+len/3)<f(r-len/3)) ans=min(ans,f(l+len/3)),r-=len/3;
		else l+=len/3,ans=min(ans,f(r-len/3));
	}
	printf("%lld",ans);
}