Description

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

\[p(a) = \sum_{i=2}^{n} (a_i - a_{i-1} - L)^2\]

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

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

Input

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

Output

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

Sample Input

4 3 1.0
1 4 5 3

Sample Output

8.000

Data Range

对于 100% 的数据, 满足:\(1 \leq n \leq 50000, 1 \leq m \leq 10^8, -100 \leq L, a_i \leq 100\)

均匀分布着 50% 的数据, 满足 \(L = 0\)

Explanation

和我口头 AC 的做法差不多:

原文链接:http://yjqqqaq.is-programmer.com/posts/183139

首先把式子拆开, 变成 \(\sum_{i=1}^{n+m}(a[i]-a[i-1])^2 - 2 * a[n] * L + 2 * a[1] * L + L^2 * (n+m-1)\)

此时​发现后面三个东西, 都不会变化 (你往两边插不会使答案变小)

然后就变成了往一个序列里面插入某些数, 使相邻两个数的平方和最小

我们考虑把相邻两个差为 \(k\) 的数中间, 插入 \(j\) 个数, 最小变成多少

显然应该均匀插入, 于是这两个数对 \(sum\) 的贡献从 \(k^2\) 变成了 \(\frac{k^2}{j+1}\)

我们考虑增量, 发现从插入 \(i\) 个数, 变成插入 \(i + 1\) 个数, 相当于是答案变小了 \(\frac{k^2}{i (i+1)}\)

然后用一个 priority_queue, 记录增量, 可以做到 \(O(m \log n)\), 但是显然是过不了的

最后发现可以二分最小的增量大小, 判断是否存在 \(m\) 个比二分的增量大的增量, 于是复杂度变成了 n*二分次数

注意二分的精度相当恶心

同时还要注意, 虽然往两边插入不会使答案变小, 但是如果最后二分出来的增量小于 \(L^2\), 可以向两边插入

也就是说我们二分的增量大小, 最小是 \(L^2\)

顺带说一句, 不开 long long 见祖宗, 十年 OI 一场空. 因为没有强制类型转换成为 double, 导致这里我再次溢出...... QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

#define sqr(__x) ((__x)*(__x))
using namespace std;
typedef long long lli;
typedef /*long*/ double llf;
const int maxn = 50010;
/*const*/ llf epsilon = 1e-14;

int n, m;
llf L, a[maxn];

int sign(llf x)
{
    if (fabs(x) < epsilon)
        return 0;
    if (x >= epsilon)
        return 1;
    return -1;
}

int get_sum(llf k, llf x)
{
    if (sign(x - k / 2.0) > 0)
        return 0;
    int p = sqrt(k / x + 0.5);
    p += 1;
    while (sign(k / (llf)(p) / (llf)(p+1) - x) < 0 && p)
        p -= 1;
    return p;
}

int eval(llf x)
{
    int res = 0;
    for (int i = 2; i <= n; i++)
        res += get_sum(sqr(a[i] - a[i-1]), x);
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d%d%lf", &n, &m, &L);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &a[i]);
    // Making initial attempts to pre-calculate result
    llf res = 0;
    for (int i = 2; i <= n; i++)
        res += sqr(a[i] - a[i-1] - L);
    // Adjusting precision in case of bugs
    if (m < 5000)
        epsilon = 1e-10;
    // Binary searching
    llf l = sqr(L), r = 1e9;
    while (sign(r - l) > 0) {
        llf mid = (l + r) / 2.0;
        if (eval(mid) < m)
            r = mid;
        else
            l = mid;
    }
    // Getting result with precalculations
    for (int i = 2; i <= n && m > 0; i++) {
        int p = get_sum(sqr(a[i] - a[i-1]), l);
        p = min(p, m);
        if (p) res = res - sqr(a[i] - a[i-1]) +
            sqr(a[i] - a[i-1]) / (p + 1) + L*L * p;
        m -= p;
    }
    // Output
    printf("%.3lf\n", res);
    return 0;
}