Fork me on GitHub

题解 P1721 【[NOI2016]国王饮水记】

其实此题根本不用那么麻烦,一个贪心即可。

贪心策略也很简单,就是原则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行代码啊?} $

最优解的代码:(为了好看我改了一点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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]);
}