「NOI2016」国王饮水记

zyxawa · 2023-02-03 15:00:59 · 个人记录

「NOI2016」国王饮水记

非常恶心的一道题目，我看了好多篇题解才懂，可能有一些和题解一样，对于 CCF 给的那一堆定理，这里没有全部用到，用到的都会解释（定理十除外）

题意：每个城市的水箱高度为 h_i，可以指定任意多的城市，将这些城市的水箱中的水变成它们的水箱高度的平均值，至多只能使用 k 次地下连通系统，求 1 号城市水箱中的水位最高能有多高

对于高度低于 h_1 的城市，可以直接舍去，因为 h_1 > h_i，容易得出 (h_1+h_i) \div 2 < h_1

此外，我们需要从小到大处理答案，可以设 h_{i1} < h_{i2} < h_{i3}，现在我们要合并它们，有 3 种方案：一次性全部合并；先合并 i1，i2，再把 i3 合并上去；先合并 i1，i3，再把 i2 合并上去（先合并 i2，i3，再把 i1 合并上去这种方案一定不是最优，和上面的定理的原因相同）

对于方案一：h_{all}=(h_{i1} + h_{i2} + h_{i3}) \div 3

对于方案二：h_{all}=(h_{i1} + h_{i2}) \div 4 + h_{i3} \div 2

对于方案三：h_{all}=(h_{i1} + h_{i3}) \div 4 + h_{i2} \div 2

将方案一和方案二比较：(h_{i1} + h_{i2} + h_{i3}) \div 3 - (h_{i1} + h_{i2}) \div 4 - h_{i3} \div 2 = (h_{i1} + h_{i2} - 2 \times h_{i3}) \div 12 < 0

将方案二和方案三比较：(h_{i1} + h_{i2}) \div 4 + h_{i3} \div 2 - (h_{i1} + h_{i3}) \div 4 - h_{i2} \div 2 = (h_{i3} - h_{i2}) \div 4 > 0

所以我们每次合并是先合并小的，在合并大的

有了以上性质，我们就可以直接 DP 了

令 dp_{i,j} 表示 前 i 个数字操作了 j 次的第一个数的最大值，sum_i=\sum_{j=1}^{i} h_j

易得 dp_{i,j} = max((dp_{l,j-1} +sum_i -sum_{l-1}) \div (i-l+1))

然后因为它在斜率优化的题单里，所以我们考虑斜率优化

同样和任务安排一样，去掉 max，发现它和普通的斜率优化不大相同，但是这里依然将 i 和 l 分开，得到 dp_{i,j} = (sum_i + (dp_{l,j-1} -sum_{l-1})) \div (i- (l-1))

于是另当前点为 (i,sum_i)，转移点为 (l-1,dp_{l,j-1} - sum_{l-1})，发现 DP 方程恰好与转移点关于当前点的斜率

因为 h_i > 0，所以 sum_i > 0，那么当前点为单调递增的，果断单调队列

所以直接维护下凸壳，因为可以发现最优答案只会在下凸壳上，那么单调队列的 tail-- 就解决了

设三个转移点 k_1 k_2 的斜率大于 k_2 k_3

假如 (i,sum_i) 在蓝线之上，说明 (i,sum_i) 与 k_3 构成的直线的斜率优于 (i,sum_i) 与 k_2，如果在红线之下，那么 (i,sum_i) 与 k_1 构成的直线的斜率优于 (i,sum_i) 与 k_2，此时 k_2 为无用转移点（这里和任务安排不同，任务安排是要求最小截距，这里是求最大斜率）

再设三个转移点 k_1 k_2 的斜率小于 k_2 k_3

此时我们发现中间是有空隙的，不能完全确定它们构成的斜率一定成大于或小于关系，都可能成为最优转移点

综上：维护下凸壳，当转移点成上凸时，需要 tail--

对于 head++，我们可以令两个转移点 k_1 优于 k_2

对于当前的 i 有：(dp_{k_1,j-1} +sum_i -sum_{k_1-1}) \div (i-k_1+1) > (dp_{k_2,j-1} +sum_i -sum_{k_2-1}) \div (i-k_2+1)

那么对于 i+1 易得：(dp_{k_1,j-1} +sum_{i+1} -sum_{k_1-1}) \div (i-k_1+2) > (dp_{k_2,j-1} +sum_{i+1} -sum_{k_2-1}) \div (i-k_2+2)

所以只要当前的一个转移点已经劣于另一个转移点，那么它就可以直接排除了

继续优化，发现 k 过于巨大，于是我们可以令 k=min(k,n)，易得这样并不会影响答案，此时还是会炸

注意到所有 h_i 互不相同，所以每一次操作的区间长度一定不比上一次操作的区间长度长，感性理解：h_i 已经排序，对于越大的数，平均分给越多的人，那么最后得到的就会更少

有了这个性质，我们找到 PPT 这句话“长度大于 1 的区间操作仅有 O(log (n \times h) \div ( min_i (h_i -h_{i-1})))”

于是 k=min(14,k)，感性理解：因为每次区间长度不会超过上一次，然后打表观察一波，最多有 14 个大于 1 的区间，严格证明（我太菜了不会啊）见此，然后改 dp_{i,j} 表示前 i 个数字选择 j 个大于 1 的区间

注意把 CCF 给的高精小数的 PREC 改成 6000

#include<bits/stdc++.h>
using namespace std;
const int PREC=6000;
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;
        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);
        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=PREC/9+1;
        static const int mo=1000000000;
        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<0){
        is_neg=true;
        x=-x;
    }
    integer=x;
}
Decimal::Decimal(long long x){
    this->init_zero();
    if(x<0){
        is_neg=true;
        x=-x;
    }
    integer=x;
}
Decimal::Decimal(double x){
    this->init_zero();
    if(x<0){
        is_neg=true;
        x=-x;
    }
    integer=(long long)x;
    x-=integer;
    for(int i=0;i<len;i++){
        x*=mo;
        if(x<0) x=0;
        data[i]=(int)x;
        x-=data[i];
    }
}
void Decimal::init_zero(){
    is_neg=false;
    integer=0;
    memset(data,0,len*sizeof(int));
}
bool Decimal::is_zero()const{
    if(integer) return false;
    for(int i=0;i<len;i++) if(data[i]) return false;
    return true;
}
void Decimal::init(const char *s){
    this->init_zero();
    is_neg=false;
    integer=0;
    while(*s!=0){
        if(*s=='-'){
            is_neg=true;
            ++s;
            break;
        }
        else if(*s>=48&&*s<=57) break;
        ++s;
    }
    while(*s>=48&&*s<=57){
        integer=integer*10+*s-48;
        ++s;
    }
    if(*s=='.'){
        int pos=0;
        int x=mo/10;
        ++s;
        while(pos<len&&*s>=48&&*s<=57){
            data[pos]+=(*s-48)*x;
            ++s;
            x/=10;
            if(x==0){
                ++pos;
                x=mo/10;
            }
        }
    }
}
void Decimal::append_to_string(std::string &s,long long x){
    if(x==0){
        s.append(1,48);
        return;
    }
    char _[30];
    int cnt=0;
    while(x){
        _[cnt++]=x%10;
        x/=10;
    }
    while(cnt--) s.append(1,_[cnt]+48);
}
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(1,'.');
    for(int i=0;i<len;i++){
        int x=mo/10;
        int tmp=data[i];
        while(x){
            ret.append(1,48+tmp/x);
            tmp%=x;
            x/=10;
            if(--p==0) break;
        }
        if(p==0) break;
    }
    if(p>0) ret.append(p,'0');
    return ret;
}
double Decimal::to_double()const{
    double ret=integer;
    double k=1.0;
    for(int i=0;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){
        if(a.integer!=b.integer) return a.integer<b.integer;
        for(int i=0;i<Decimal::len;i++) if(a.data[i]!=b.data[i]) return a.data[i]<b.data[i];
        return false;
    }
    else{
        if(a.integer!=b.integer) return a.integer>b.integer;
        for(int i=0;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){
        if(a.integer!=b.integer) return a.integer>b.integer;
        for(int i=0;i<Decimal::len;i++) if(a.data[i]!=b.data[i]) return a.data[i]>b.data[i];
        return false;
    }
    else{
        if(a.integer!=b.integer) return a.integer<b.integer;
        for(int i=0;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){
        if(a.integer!=b.integer) return a.integer<b.integer;
        for(int i=0;i<Decimal::len;i++) if(a.data[i]!=b.data[i]) return a.data[i]<b.data[i];
        return true;
    }
    else{
        if(a.integer!=b.integer) return a.integer>b.integer;
        for(int i=0;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){
        if(a.integer!=b.integer) return a.integer>b.integer;
        for(int i=0;i<Decimal::len;i++) if(a.data[i]!=b.data[i]) return a.data[i]>b.data[i];
        return true;
    }
    else{
        if(a.integer!=b.integer) return a.integer<b.integer;
        for(int i=0;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=0;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>=0) integer+=x;
        else{
            bool last=false;
            for(int i=len-1;i>=0;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>=0) integer-=x;
        else{
            bool last=false;
            for(int i=len-1;i>=0;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<0){
        is_neg^=1;
        x=-x;
    }
    int last=integer%x;
    integer/=x;
    for(int i=0;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==0){
        int i;
        for(i=0;i<len;i++) if(data[i]!=0) break;
        if(i==len) is_neg=false;
    }
    return *this;
}
Decimal&Decimal::operator*=(int x){
    if(x<0){
        is_neg^=1;
        x=-x;
    }
    else if(x==0){
        init_zero();
        return *this;
    }
    int last=0;
    for(int i=len-1;i>=0;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;
    if(!ret.is_neg&&ret.integer== 0){
        int i;
        for(i=0;i<Decimal::len;i++) if(ret.data[i]!=0) break;
        if(i<Decimal::len) ret.is_neg=true;
    }
    else ret.is_neg^=1;
    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-1;i>=0;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) return a- -b;
    else 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-1;i>=0;i--){
                ret.data[i]-=b.data[i]+last;
                if(ret.data[i]<0){
                    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-1;i>=0;i--){
                ret.data[i]-=a.data[i]+last;
                if(ret.data[i]<0){
                    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) return -b- -a;
    else if(a.is_neg) return -(-a+b);
    else 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 ans;
int n,k,p,t,st,lim,head,tail,h[8001],q[8001],to[8001][15];
double aus,dp[8001][15],s[8001];
pair <double,double> a,b[8001];
double val(pair <double,double> p,pair <double,double> q){
    return(q.second-p.second)/(q.first-p.first);
}
Decimal calc(int i,int j){
    if(!j) return h[1];
    else return (calc(to[i][j],j-1)+s[i]-s[to[i][j]])/(i-to[i][j]+1);
}
int main(){
    scanf("%d%d%d%d",&n,&k,&p,&h[1]);
    for(int i=2;i<=n;i++){
        scanf("%d",&h[i]);
        if(h[i]<=h[1]) i--,n--;
    }
    sort(h+1,h+1+n);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+h[i],dp[i][0]=h[1];
    k=min(k,n);
    lim=min(14,k);
    t=n-(k-lim);
    for(int j=1;j<=lim;j++){
        q[head=tail=1]=1;
        b[1]={0,s[1]-dp[1][j-1]};
        for(int i=2;i<=n;i++){
            a={i,s[i]};
            while(head<tail&&val(b[q[head]],a)<=val(b[q[head+1]],a)) head++;
            b[i]={i-1,s[i]-dp[i][j-1]};
            to[i][j]=q[head];
            dp[i][j]=(1.0*(s[i]-s[q[head]]+dp[q[head]][j-1]))/(1.0*(i-q[head]+1));
            while(head<tail&&val(b[q[tail-1]],b[q[tail]])>=val(b[q[tail]],b[i])) tail--;
            q[++tail]=i;
        }
    }
    for(int i=0;i<=lim;i++) if(dp[t][i]>aus) aus=dp[t][i],st=i;
    ans=calc(t,st);
    for(int i=t+1;i<=n;i++) ans=(ans+h[i])/2;
    cout<<ans.to_string(p*6/5);
    return 0;
}