[NOI2016]国王饮水记

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

输入的第一行包含 3 个正整数 n,k,p分别表示跳蚤国中城市的数量，跳蚤国王能使用地下连通系统的最多次数，以及你输出的答案要求的精度。p 的含义将在输出格式中解释。接下来一行包含 n 个正整数，描述城市的水箱在雨后的水位。其中第 i 个正整数 hi 表示第 i 个城市的水箱的水位。保证 hi 互不相同，1≤hi≤10^5
对于所有数据，满足3≤p≤3000,1≤n≤8000,1≤k≤10^9

仅一行一个实数，表示 1 号城市的水箱中的最高水位。这个实数只可以包含非负整数部分、小数点和小数部分。
其中非负整数部分为必需部分，不加正负号。若有小数部分，则非负整数部分与小数部分之间以一个小数点隔开。
若无小数部分，则不加小数点。你输出的实数在小数点后不能超过 2p 位，建议保留至少 p 位。数据保证参考答案与真实答案的绝对误差小于 10^-2p。你的输出被判定为正确当且仅当你的输出与参考答案的绝对误差小于 10^-p

#include<bits/stdc++.h> int N,n,m,p; int h[8192],s[8192]; double f[16][8192]; int g[16][8192]; int a[400]; using namespace std; #define P pair<int,double> double operator%(const P&a,const P&b) { return (b.second-a.second)/(b.first-a.first); } void div(int x) { long long q=0; for(int i=0;i<=p;i++) { q=q*1000000000+a[i]; a[i]=q/x; q%=x; } } int main() { scanf("%d%d%d",&N,&m,&p); p=p/9+1; scanf("%d",&h[n=1]); for(int i=2;i<=N;i++) { int t; scanf("%d",&t); if(h[1]<t) h[++n]=t; } sort(h+1,h+n+1); if(m>n) m=n; for(int i=1;i<=n;i++) f[0][i]=h[1],s[i]=s[i-1]+h[i]; int l=14; if(l>m) l=m; for(int i=1;i<=l;i++) { static P q[8024]; for(int j=2,l=1,r=0;j<=n;j++) { P c=P(j-2,s[j-1]-f[i-1][j-1]); for(;l<r&&(q[r-1]%q[r])>(q[r]%c);r--); q[++r]=c; P t=P(j,s[j]); for(;l<r&&(q[l]%t)<(q[l+1]%t);l++); g[i][j]=q[l].first+1; f[i][j]=(q[l]%t); } } int _[16]; _[l]=n-(m-l); for(int i=l;i;i--) _[i-1]=g[i][_[i]]; a[0]=h[1]; for(int i=1;i<=l;i++) a[0]+=s[_[i]]-s[_[i-1]],div(_[i]-_[i-1]+1); for(int i=_[l]+1;i<=n;i++) a[0]+=h[i],div(2); printf("%d.",a[0]); for(int i=1;i<=p;i++) printf("%09d",a[i]); }

详情