[Noi2016]国王饮水记

来自FallDream的博客，未经允许，请勿转载，谢谢。

---

跳蚤国有 n 个城市，伟大的跳蚤国王居住在跳蚤国首都中，即 1 号城市中。跳蚤国最大的问题就是饮水问题，由于首都中居住的跳蚤实在太多，跳蚤国王又体恤地将分配给他的水也给跳蚤国居民饮用，这导致跳蚤国王也经常喝不上水。于是，跳蚤国在每个城市都修建了一个圆柱形水箱，这些水箱完全相同且足够高。一个雨天后，第 i 个城市收集到了高度为 hi 的水。由于地理和天气因素的影响，任何两个不同城市收集到的水高度互不相同。跳蚤国王也请来蚂蚁工匠帮忙，建立了一个庞大的地下连通系统。跳蚤国王每次使用地下连通系统时，可以指定任意多的城市，将这些城市的水箱用地下连通系统连接起来足够长的时间之后，再将地下连通系统关闭。由连通器原理，这些城市的水箱中的水在这次操作后会到达同一高度，并且这一高度等于指定的各水箱高度的平均值。由于地下连通系统的复杂性，跳蚤国王至多只能使用 k 次地下连通系统。跳蚤国王请你告诉他，首都 1 号城市水箱中的水位最高能有多高？

n<=8000 hi<=10^5

至少保留p位小数 p<=3000

提供了一个高精度小数类

首先考虑只保留大于1号城市的高度，并且发现从小到大合并比较优秀 所以按照从小到大排序 求出前缀和Hi

然后每次都计算太麻烦了，所以用一个trick，先用long double计算出转移路径再计算答案 (题解里面一套分数类啥的可以直接做)

列出转移方程$f[k][i]=max(\frac{f[k-1][j]+si-sj}{i-j+1})$ 考虑维护(j-1,sj-f[k-1][j])的下凸壳，发现它满足决策单调性 于是复杂度降低至$O(n^{2}+np)$

但是根据题解里面一系列的结论，每次取的长度不同且递减，长度大于1的最多只有14个，所以先dp出14层，然后剩下的直接两两合并就行了。复杂度Ｏ(14n+np)

// This is a test program with decimal lib

#include <cstdlib>
#include <cstring>
#include <string>

// ---------- decimal lib start ----------

const int PREC = ;

class Decimal {
    public:
        Decimal();
        Decimal(const std::string &s);
        Decimal(const char *s);
        Decimal(int x);
        Decimal(long long x);
        Decimal(double x);

        bool is_zero() const;

        // p (p > 0) is the number of digits after the decimal point
        std::string to_string(int p) const;
        double to_double() const;

        friend Decimal operator + (const Decimal &a, const Decimal &b);
        friend Decimal operator + (const Decimal &a, int x);
        friend Decimal operator + (int x, const Decimal &a);
        friend Decimal operator + (const Decimal &a, long long x);
        friend Decimal operator + (long long x, const Decimal &a);
        friend Decimal operator + (const Decimal &a, double x);
        friend Decimal operator + (double x, const Decimal &a);

        friend Decimal operator - (const Decimal &a, const Decimal &b);
        friend Decimal operator - (const Decimal &a, int x);
        friend Decimal operator - (int x, const Decimal &a);
        friend Decimal operator - (const Decimal &a, long long x);
        friend Decimal operator - (long long x, const Decimal &a);
        friend Decimal operator - (const Decimal &a, double x);
        friend Decimal operator - (double x, const Decimal &a);

        friend Decimal operator * (const Decimal &a, int x);
        friend Decimal operator * (int x, const Decimal &a);

        friend Decimal operator / (const Decimal &a, int x);

        friend bool operator < (const Decimal &a, const Decimal &b);
        friend bool operator > (const Decimal &a, const Decimal &b);
        friend bool operator <= (const Decimal &a, const Decimal &b);
        friend bool operator >= (const Decimal &a, const Decimal &b);
        friend bool operator == (const Decimal &a, const Decimal &b);
        friend bool operator != (const Decimal &a, const Decimal &b);

        Decimal & operator += (int x);
        Decimal & operator += (long long x);
        Decimal & operator += (double x);
        Decimal & operator += (const Decimal &b);

        Decimal & operator -= (int x);
        Decimal & operator -= (long long x);
        Decimal & operator -= (double x);
        Decimal & operator -= (const Decimal &b);

        Decimal & operator *= (int x);

        Decimal & operator /= (int x);

        friend Decimal operator - (const Decimal &a);

        // These can't be called
        friend Decimal operator * (const Decimal &a, double x);
        friend Decimal operator * (double x, const Decimal &a);
        friend Decimal operator / (const Decimal &a, double x);
        Decimal & operator *= (double x);
        Decimal & operator /= (double x);

    private:
        static const int len = ;
        static const int mo = ;

        static void append_to_string(std::string &s, long long x);

        bool is_neg;
        long long integer;
        int data[len];

        void init_zero();
        void init(const char *s);
};

Decimal::Decimal() {
    this->init_zero();
}

Decimal::Decimal(const char *s) {
    this->init(s);
}

Decimal::Decimal(const std::string &s) {
    this->init(s.c_str());
}

Decimal::Decimal(int x) {
    this->init_zero();

    if (x < ) {
        is_neg = true;
        x = -x;
    }

    integer = x;
}

Decimal::Decimal(long long x) {
    this->init_zero();

    if (x < ) {
        is_neg = true;
        x = -x;
    }

    integer = x;
}

Decimal::Decimal(double x) {
    this->init_zero();

    if (x < ) {
        is_neg = true;
        x = -x;
    }

    integer = (long long)x;
    x -= integer;

    for (int i = ; i < len; i++) {
        x *= mo;
        if (x < ) x = ;
        data[i] = (int)x;
        x -= data[i];
    }
}

void Decimal::init_zero() {
    is_neg = false;
    integer = ;
    memset(data, , len * sizeof(int));
}

bool Decimal::is_zero() const {
    if (integer) return false;
    for (int i = ; i < len; i++) {
        if (data[i]) return false;
    }
    return true;
}

void Decimal::init(const char *s) {
    this->init_zero();

    is_neg = false;
    integer = ;

    // find the first digit or the negative sign
    while (*s != ) {
        if (*s == '-') {
            is_neg = true;
            ++s;
            break;
        } else if (*s >=  && *s <= ) {
            break;
        }
        ++s;
    }

    // read the integer part
    while (*s >=  && *s <= ) {
        integer = integer *  + *s - ;
        ++s;
    }

    // read the decimal part
    if (*s == '.') {
        int pos = ;
        int x = mo / ;

        ++s;
        while (pos < len && *s >=  && *s <= ) {
            data[pos] += (*s - ) * x;
            ++s;
            x /= ;
            if (x == ) {
                ++pos;
                x = mo / ;
            }
        }
    }
}

void Decimal::append_to_string(std::string &s, long long x) {
    if (x == ) {
        s.append(, );
        return;
    }

    char _[];
    int cnt = ;
    while (x) {
        _[cnt++] = x % ;
        x /= ;
    }
    while (cnt--) {
        s.append(, _[cnt] + );
    }
}

std::string Decimal::to_string(int p) const {
    std::string ret;

    if (is_neg && !this->is_zero()) {
        ret = "-";
    }

    append_to_string(ret, this->integer);

    ret.append(, '.');

    for (int i = ; i < len; i++) {
        // append data[i] as "%09d"
        int x = mo / ;
        int tmp = data[i];
        while (x) {
            ret.append(,  + tmp / x);
            tmp %= x;
            x /= ;
            if (--p == ) {
                break;
            }
        }
        if (p == ) break;
    }

    if (p > ) {
        ret.append(p, '');
    }

    return ret;
}

double Decimal::to_double() const {
    double ret = integer;

    double k = 1.0;
    for (int i = ; i < len; i++) {
        k /= mo;
        ret += k * data[i];
    }

    if (is_neg) {
        ret = -ret;
    }

    return ret;
}

bool operator < (const Decimal &a, const Decimal &b) {
    if (a.is_neg != b.is_neg) {
        return a.is_neg && (!a.is_zero() || !b.is_zero());
    } else if (!a.is_neg) {
        // a, b >= 0
        if (a.integer != b.integer) {
            return a.integer < b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] < b.data[i];
            }
        }
        return false;
    } else {
        // a, b <= 0
        if (a.integer != b.integer) {
            return a.integer > b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] > b.data[i];
            }
        }
        return false;
    }
}

bool operator > (const Decimal &a, const Decimal &b) {
    if (a.is_neg != b.is_neg) {
        return !a.is_neg && (!a.is_zero() || !b.is_zero());
    } else if (!a.is_neg) {
        // a, b >= 0
        if (a.integer != b.integer) {
            return a.integer > b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] > b.data[i];
            }
        }
        return false;
    } else {
        // a, b <= 0
        if (a.integer != b.integer) {
            return a.integer < b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] < b.data[i];
            }
        }
        return false;
    }
}

bool operator <= (const Decimal &a, const Decimal &b) {
    if (a.is_neg != b.is_neg) {
        return a.is_neg || (a.is_zero() && b.is_zero());
    } else if (!a.is_neg) {
        // a, b >= 0
        if (a.integer != b.integer) {
            return a.integer < b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] < b.data[i];
            }
        }
        return true;
    } else {
        // a, b <= 0
        if (a.integer != b.integer) {
            return a.integer > b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] > b.data[i];
            }
        }
        return true;
    }
}

bool operator >= (const Decimal &a, const Decimal &b) {
    if (a.is_neg != b.is_neg) {
        return !a.is_neg || (a.is_zero() && b.is_zero());
    } else if (!a.is_neg) {
        // a, b >= 0
        if (a.integer != b.integer) {
            return a.integer > b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] > b.data[i];
            }
        }
        return true;
    } else {
        // a, b <= 0
        if (a.integer != b.integer) {
            return a.integer < b.integer;
        }
        for (int i = ; i < Decimal::len; i++) {
            if (a.data[i] != b.data[i]) {
                return a.data[i] < b.data[i];
            }
        }
        return true;
    }
}

bool operator == (const Decimal &a, const Decimal &b) {
    if (a.is_zero() && b.is_zero()) return true;
    if (a.is_neg != b.is_neg) return false;
    if (a.integer != b.integer) return false;
    for (int i = ; i < Decimal::len; i++) {
        if (a.data[i] != b.data[i]) return false;
    }
    return true;
}

bool operator != (const Decimal &a, const Decimal &b) {
    return !(a == b);
}

Decimal & Decimal::operator += (long long x) {
    if (!is_neg) {
        if (integer + x >= ) {
            integer += x;
        } else {
            bool last = false;
            for (int i = len - ; i >= ; i--) {
                if (last || data[i]) {
                    data[i] = mo - data[i] - last;
                    last = true;
                } else {
                    last = false;
                }
            }
            integer = -x - integer - last;
            is_neg = true;
        }
    } else {
        if (integer - x >= ) {
            integer -= x;
        } else {
            bool last = false;
            for (int i = len - ; i >= ; i--) {
                if (last || data[i]) {
                    data[i] = mo - data[i] - last;
                    last = true;
                } else {
                    last = false;
                }
            }
            integer = x - integer - last;
            is_neg = false;
        }
    }
    return *this;
}

Decimal & Decimal::operator += (int x) {
    return *this += (long long)x;
}

Decimal & Decimal::operator -= (int x) {
    return *this += (long long)-x;
}

Decimal & Decimal::operator -= (long long x) {
    return *this += -x;
}

Decimal & Decimal::operator /= (int x) {
    if (x < ) {
        is_neg ^= ;
        x = -x;
    }

    int last = integer % x;
    integer /= x;

    for (int i = ; i < len; i++) {
        long long tmp = 1LL * last * mo + data[i];
        data[i] = tmp / x;
        last = tmp - 1LL * data[i] * x;
    }

    if (is_neg && integer == ) {
        int i;
        for (i = ; i < len; i++) {
            if (data[i] != ) {
                break;
            }
        }
        if (i == len) {
            is_neg = false;
        }
    }

    return *this;
}

Decimal & Decimal::operator *= (int x) {
    if (x < ) {
        is_neg ^= ;
        x = -x;
    } else if (x == ) {
        init_zero();
        return *this;
    }

    int last = ;
    for (int i = len - ; i >= ; i--) {
        long long tmp = 1LL * data[i] * x + last;
        last = tmp / mo;
        data[i] = tmp - 1LL * last * mo;
    }
    integer = integer * x + last;

    return *this;
}

Decimal operator - (const Decimal &a) {
    Decimal ret = a;
    // -0 = 0
    if (!ret.is_neg && ret.integer == ) {
        int i;
        for (i = ; i < Decimal::len; i++) {
            if (ret.data[i] != ) break;
        }
        if (i < Decimal::len) {
            ret.is_neg = true;
        }
    } else {
        ret.is_neg ^= ;
    }
    return ret;
}

Decimal operator + (const Decimal &a, int x) {
    Decimal ret = a;
    return ret += x;
}

Decimal operator + (int x, const Decimal &a) {
    Decimal ret = a;
    return ret += x;
}

Decimal operator + (const Decimal &a, long long x) {
    Decimal ret = a;
    return ret += x;
}

Decimal operator + (long long x, const Decimal &a) {
    Decimal ret = a;
    return ret += x;
}

Decimal operator - (const Decimal &a, int x) {
    Decimal ret = a;
    return ret -= x;
}

Decimal operator - (int x, const Decimal &a) {
    return -(a - x);
}

Decimal operator - (const Decimal &a, long long x) {
    Decimal ret = a;
    return ret -= x;
}

Decimal operator - (long long x, const Decimal &a) {
    return -(a - x);
}

Decimal operator * (const Decimal &a, int x) {
    Decimal ret = a;
    return ret *= x;
}

Decimal operator * (int x, const Decimal &a) {
    Decimal ret = a;
    return ret *= x;
}

Decimal operator / (const Decimal &a, int x) {
    Decimal ret = a;
    return ret /= x;
}

Decimal operator + (const Decimal &a, const Decimal &b) {
    if (a.is_neg == b.is_neg) {
        Decimal ret = a;
        bool last = false;
        for (int i = Decimal::len - ; i >= ; i--) {
            ret.data[i] += b.data[i] + last;
            if (ret.data[i] >= Decimal::mo) {
                ret.data[i] -= Decimal::mo;
                last = true;
            } else {
                last = false;
            }
        }
        ret.integer += b.integer + last;
        return ret;
    } else if (!a.is_neg) {
        // a - |b|
        return a - -b;
    } else {
        // b - |a|
        return b - -a;
    }
}

Decimal operator - (const Decimal &a, const Decimal &b) {
    if (!a.is_neg && !b.is_neg) {
        if (a >= b) {
            Decimal ret = a;
            bool last = false;
            for (int i = Decimal::len - ; i >= ; i--) {
                ret.data[i] -= b.data[i] + last;
                if (ret.data[i] < ) {
                    ret.data[i] += Decimal::mo;
                    last = true;
                } else {
                    last = false;
                }
            }
            ret.integer -= b.integer + last;
            return ret;
        } else {
            Decimal ret = b;
            bool last = false;
            for (int i = Decimal::len - ; i >= ; i--) {
                ret.data[i] -= a.data[i] + last;
                if (ret.data[i] < ) {
                    ret.data[i] += Decimal::mo;
                    last = true;
                } else {
                    last = false;
                }
            }
            ret.integer -= a.integer + last;
            ret.is_neg = true;
            return ret;
        }
    } else if (a.is_neg && b.is_neg) {
        // a - b = (-b) - (-a)
        return -b - -a;
    } else if (a.is_neg) {
        // -|a| - b
        return -(-a + b);
    } else {
        // a - -|b|
        return a + -b;
    }
}

Decimal operator + (const Decimal &a, double x) {
    return a + Decimal(x);
}

Decimal operator + (double x, const Decimal &a) {
    return Decimal(x) + a;
}

Decimal operator - (const Decimal &a, double x) {
    return a - Decimal(x);
}

Decimal operator - (double x, const Decimal &a) {
    return Decimal(x) - a;
}

Decimal & Decimal::operator += (double x) {
    *this = *this + Decimal(x);
    return *this;
}

Decimal & Decimal::operator -= (double x) {
    *this = *this - Decimal(x);
    return *this;
}

Decimal & Decimal::operator += (const Decimal &b) {
    *this = *this + b;
    return *this;
}

Decimal & Decimal::operator -= (const Decimal &b) {
    *this = *this - b;
    return *this;
}

// ---------- decimal lib end ----------
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define MN 8000
#define ld long double

inline int read()
{
    int x =  , f = ; char ch = getchar();
    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}
    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}
    return x * f;
}
int n , m , k , K , p , h[MN + ] , Pre , top , From[][MN + ];
ld f[][MN + ];
struct P
{
    int x; ld y;
    P(int _x = ,ld _y = ): x(_x) , y(_y) {}
    friend ld Calc(P a , P b)
    {
        return (b.y - a.y) / (b.x - a.x);
    }
};

struct MyQueue
{
    P q[MN + ];int top , tail;
    void Clear(){ q[top = tail = ] = P( - , -Pre);}
    void ins(P t)
    {
        while(top > tail && Calc(q[top-] , q[top]) > Calc(q[top] , t)) --top;
        q[ ++top ] = t;
    }
    int Query(P t)
    {
        while(top > tail && Calc(q[tail] , t) < Calc(q[tail + ] , t)) ++tail;
        return q[tail].x + ;
    }
}Q;

Decimal Ans;

void Dfs(int t , int x)
{
    if(!t) return;
    Dfs( t -  , From[t][x] );
    Ans = ( Ans + h[x] - h[From[t][x]] ) / (x - From[t][x] + );
}

int main() {
    m = read(); K = read(); p = read(); Pre = read();
    for(int i =  , j;i < m ;++i)
        if((j = read()) > Pre) h[++n] = j;
    sort(h+ , h + n + ); K = min(K , n); k = min(K , );
    for(int i =  ;i <= n ;++i) h[i] += h[i-] , f[][i] = Pre;h[] = -Pre;
    for(int j = ;j <= k ;++j)
    {
        Q.Clear();
        for(int i =  ;i <= n ; ++i)
        {
            From[j][i] = Q.Query(P(i , h[i]));
            f[j][i] = (f[j - ][From[j][i]] + h[i] - h[ From[j][i] ]) / (i - From[j][i] + );
            Q.ins(P(i -  , h[i] - f[j - ][i]));
        }
    }
    Ans = Decimal ( Pre ); h[] = ;
    Dfs ( k , n - (K - k) );
    for(int i = n - (K - k) + ;i <= n ; ++i) Ans = (Ans + h[i] - h[i-]) / ;
    cout << Ans.to_string(p + );
    return ;
}