记录编号	242541	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]刷题计划	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.644 s
提交时间	2016-03-27 17:31:39	内存使用	1.27 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int SIZEN=50010,INF=0x7fffffff/2;
const double zero=1e-13;
int N,M;
double L;
double a[SIZEN];
double d[SIZEN];
double sqr(double x)
{
	return x*x;
}
void read()
{
	scanf("%d%d",&N,&M);
	scanf("%lf",&L);
	for(int i=1;i<=N;i++) scanf("%lf",&a[i]),d[i]=a[i]-a[i-1];
}
int piece[SIZEN];
double Calc_cost(double a,double y)//把a分成y个段的代价
{
	double re=a*a/y-2.0*a*L+y*L*L;
	return re;
}
int cut(double d,double x)//初中知识...
{
	double t=sqr(d)/(sqr(L)-x);
	if(t<=0) return 1;
	//cout<<t<<endl;
	double ans=(sqrt(4*t+1)-1)/2.0;
	return max(ceil(ans),1.0);
}
int Calc_sum(double x)//把所有的区间的增量变成x的切割次数
{
	int ans=0;
	for(int i=2;i<=N;i++)
	{
		int tem=cut(d[i],x);
		piece[i]=tem;
		ans+=tem-1;
	}
	return ans;
}
double get()//
{
	double ans=0;
	for(int i=2;i<=N;i++) ans+=Calc_cost(d[i],piece[i]);
	return ans;
}
void work()
{
	double ma=-INF;
	for(int i=2;i<=N;i++)
		ma=max(d[i],ma);
	//cout<<ma<<endl;
	double l=sqr(L)-sqr(ma)*(0.5),r=0.0;
	double ans=0;
	if(l>=r)//不用加点已经是最优的
	{
		for(int i=2;i<=N;i++) piece[i]=1;
		ans=get();
		printf("%.3lf\n",ans);
		return;
	}
	int tot=0;
	while(++tot<=100)
	{
		double mid=(r+l)/2.0;
		int tem=Calc_sum(mid);
		if(tem>M) r=mid;
		else l=mid;
	}
	Calc_sum(l);
	//for(int i=1;i<=N;i++) cout<<piece[i]<<" ";
	//cout<<endl;
	ans=get();
	printf("%.3lf\n",ans);
}
int main()
{
	freopen("nt2011_seq.in","r",stdin);
	freopen("nt2011_seq.out","w",stdout);
	read();
	work();
	return 0;
}