1883. [国家集训队2011]刷题计划

【问题描述】

为了提高自己的实力，gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度，并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式，最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到，于是我们定义一个刷题序列a的偏离值 ，其中L是给定的一个常数。
现在gx的老师已经布置给了他n道必做题，同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序，但是选做题的难度以及在数列中的位置都是任意的（OJ上的题目太多了，随你怎么挑）。
gx希望你帮他设计一个刷题序列，使得该序列的偏离值最小。

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【样例说明】

【数据规模和约定】

【问题描述】

为了提高自己的实力，gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度，并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式，最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到，于是我们定义一个刷题序列a的偏离值 ，其中L是给定的一个常数。

现在gx的老师已经布置给了他n道必做题，同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序，但是选做题的难度以及在数列中的位置都是任意的（OJ上的题目太多了，随你怎么挑）。

gx希望你帮他设计一个刷题序列，使得该序列的偏离值最小。

【输入格式】

输入的第一行包含三个数：n, m, L。n是整数，表示必做题有n道，m是整数，表示选做题有m道，L是实数。第二行包含n个实数，依次表示每道必做题的难度。

【输出格式】

输出一个实数，表示最小的偏离值。保留三位小数。

【样例输入】

4 3 1.0

1 4 5 3

【样例输出】

8.000

【样例说明】

将原序列(1,4,5,3)变成(1,2,3,4,5,4,3)，偏离值为8.00。

【数据范围】

对于30%的数据 n≤500, m≤200

对于70%的数据 n≤20000, m≤100000

对于100%的数据 1≤n≤50000, 1≤m≤100000000, -100≤L≤100, |a_i|≤100

均匀分布着50%的数据 L=0