记录编号	143714	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]刷题计划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.652 s
提交时间	2014-12-17 10:39:42	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
#define sqr(x) ((x)*(x))
const int SIZEN=50010;
const double INF=1e10;
int N,M;
double L;
double A[SIZEN];
double dif[SIZEN];
LL calc_single_num(double a,double dt){//差为a,增量>=dt(增量是负的),最少需要切成几段
	double t=sqr(a)/(sqr(L)-dt);//k*(k+1)>=t的最小整数k
	if(t<=0) return 1;
	double x=(sqrt(4*t+1)-1)/2;
	return max(ceil(x),1.0);
}
LL calc_num(double dt,LL cnt[]){//增量>=dt,需要多少个题库中的题
	LL ans=0;
	for(int i=1;i<N;i++){
		cnt[i]=calc_single_num(dif[i],dt);
		ans+=cnt[i]-1;
	}
	return ans;
}
double calc_delta(double a,int k){//切成k+1段与k段相比的增量
	return sqr(L)-sqr(a)/(k*(k+1));
}
double calc_cost(double a,int k){//切成k段的耗费
	return sqr(a)/k-2*a*L+sqr(L)*k;
}
void answer(LL cnt[]){
	double ans=0;
	for(int i=1;i<N;i++) ans+=calc_cost(dif[i],cnt[i]);
	printf("%.3lf\n",ans);
}
void work(void){
	double mndif=INF,mxdif=-INF;
	for(int i=1;i<N;i++){
		mndif=min(mndif,fabs(dif[i]));
		mxdif=max(mxdif,dif[i]);
	}
	double l=calc_delta(mxdif,1),r=0;
	static LL cnt[SIZEN];
	if(l>=r){
		calc_num(0.0,cnt);
		answer(cnt);
		return;
	}
	int tot=0;
	while(++tot<=100){//二分最小增量
		double mid=(l+r)/2;
		LL now=calc_num(mid,cnt);
		if(now>M) r=mid;
		else l=mid;
	}
	calc_num(l,cnt);
	answer(cnt);
}
void read(void){
	scanf("%d%d",&N,&M);
	scanf("%lf",&L);
	for(int i=1;i<=N;i++) scanf("%lf",&A[i]);
	for(int i=1;i<N;i++) dif[i]=A[i+1]-A[i];
}
int main(){
	freopen("nt2011_seq.in","r",stdin);
	freopen("nt2011_seq.out","w",stdout);
	read();
	work();
	return 0;
}