题解 P1721 【[NOI2016]国王饮水记】
引领天下
2018-07-31 16:21:29
其实此题根本不用那么麻烦，一个贪心即可。
贪心策略也很简单，就是**原则1：能连2个不连3个**
为什么呢？我们举例验证。
例：$n=3,h1=1,h2=1.7,h3=3$
这时，如果连通1、2、3，水位为$ \frac{1+1.7+3}{3}=1.9 $，而如果连通1、3，水位为$ \frac{1+3}{2}=2$，这时，由于2的水位低于平均数，所以2反而拖了后腿。
有没有办法利用2呢？
有。
如果先连通1、2，水位为$\frac{1+1.7}{2}=1.35 $，再连通1、3，水位为$\frac{1.35+3}{2}=2.175$，比刚才高。
所以得到一个推论：**原则2：如果要加入一个城市进入连通器，它的水位一定要比已有平均数高**
在一般情况下，尽量一次连2个；如果k不够用，则用原则2，将2次的连通并为一次。
接下来就是难点：恶心~~毒瘤~~的保留p位小数的高精除。$ \color{black} \colorbox{black}{所以根本不用写700行代码啊？} $
最优解的代码：（为了好看我改了一点）
```cpp
#include<bits/stdc++.h>
int N,n,m,p;
int h[8192],s[8192];//8192=2<<13
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]);
}
```