自动搬运

查看原文

来自洛谷，原作者为

	yybyyb **

搬运于2025-08-24 21:28:18，当前版本为作者最后更新于2018-07-12 22:27:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷的$Markdown$换行什么的很迷啊，如果看得不舒服直接到我的博客 去看吧。。。。

首先肯定是找性质。 明确一点，比$h_1$小的没有任何意义。 所以我们按照$h$排序，那么$h_1$就是当前$1$号位置的水量。 假设我们使用的次数不受到任何限制，我们思考怎么样才是最优。 首先每次只和一个合并一定比和多个合并更优。 假设有三个位置$h_1\lt h_2\lt h_3$ 那么如果直接合并，答案是$(h_1+h_2+h_3)/3$ 如果每次合并一个，答案是$((h_1+h_2)/2+h_3)/2=(h_1+h_2)/4+h_3/2$ 显然后者更优。 同理，通过后面那个式子，我们发现先和$h_2$合并比先和$h_3$合并更优。 所以，在合并次数不受到限制的时候，我们显然是从小往大，依次合并。

当次数不够的时候，我们肯定不能只合并一个位置，显然合并所有位置还是更优的。 那么，既然不能够一个个合并，所以只能够把若干次合并放在一起做。 因为每次和后面的若干个做完合并之后，这些一起合并的位置就可以直接丢掉了， 再因为从小往大合并更优，假设$h_i$已经有序，那么每次一定是和一段合并。 所以设$f[i][j]$表示前面$i$个位置合并了$j$次的最优值。 那么考虑转移$f[i][j]=max((f[k][j-1]+\sum_{x\in[k+1,i]}h_x)/(i-k+1)$ 这样的复杂度$O(n^2k)$，$k$是可以合并的次数。 把式子重写，$\sum$写成前缀和的形式，暂时忽略后面的枚举次数 $f[i]=(f[k]+s[i]-s[k])/(i-k+1)$ 这个式子很像斜率： $(s[i]-(s[k]-f[k]))/(i-(k-1))$ 相当于把前面所有已知状态看成一个点$(k-1,s[k]-f[k])$ 那么找到当前点$(i,s[i])$到这个点的斜率，使其斜率最大，可以斜率优化解决。 这样可以在凸包上三分计算，时间复杂度$O(nklog_3n)$ 因为给定的高精小数库还有一个$O(p)$的复杂度，所以整个的复杂度是$O(nkplogn)$ 同时还发现具有决策单调性，所以可以做到$O(nkp)$ 决策单调性的证明大概是这样的，假设当位置是$(i,s[i])$ 最优转移是$(x1,y1)$，存在一个不优的转移$(x2,y2)$， 根据题目条件，有$i>x1>x2,s[i]>y1>y2,s[i]>i,y1>x1,y2>x2$ 一下个位置至少是$(i+1,s[i]+i)$，然后把斜率的式子写一写发现$(x1,y1)$仍然更优。

现在可以做到$O(nkp)$，但是这样的复杂度远远不够。 继续挖掘性质。 发现有一个条件我们还没有怎么使用，即所有$h_i$互不相等。 那么我们可以得到一个条件：每次转移的区间长度不会大于上一次转移的区间长度。 感性的证明就是越往后走高度越大，显然拿更少的位置来平分会更优。 或者可以假设一下区间的长度，然后计算一下结果就好了。 或者假如后面那个区间长度大于前面这个区间，那么把后面那个区间的最前面那个位置分给前面这一段一定更优。 还有一个奇怪的条件：长度大于$1$的区间个数不会超过$O(log\frac{nh}{\Delta})$，其中$\Delta=min(h_i-h_{i-1})$ 证明？我不会我不会，可以参考这里的证明

那么这样子，只需要$dp$大概$14$层就好啦。（参考征途或者序列分割之类的题目）

完整的代码戳这里

以下是阉割版本。毕竟放个700行的代码翻都翻不完

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAX=8080;
Decimal ans;
int n,K,p,h[MAX],zy[MAX][15],s[MAX],tot;
int Q[MAX],H,T;
double f[MAX][15];
struct Node{double x,y;}q[MAX];
double Slope(Node a,Node b){return (a.y-b.y)/(a.x-b.x);}
Decimal Calc(int i,int j)
{
	if(!j)return h[1];
	return (Calc(zy[i][j],j-1)+s[i]-s[zy[i][j]])/(i-zy[i][j]+1);
}
int main()
{
	n=read();K=read();p=read();h[tot=1]=read();
	for(int i=2;i<=n;++i)
	{
		h[i]=read();
		if(h[i]>h[1])h[++tot]=h[i];
	}
	n=tot;sort(&h[1],&h[n+1]);
	for(int i=1;i<=n;++i)s[i]=s[i-1]+h[i];
	K=min(K,n);
	for(int i=1;i<=n;++i)f[i][0]=h[1];
	int lim=min(K,14);
	for(int j=1;j<=lim;++j)
	{
		Q[H=T=1]=1;
		for(int i=1;i<=n;++i)q[i]=(Node){i-1,s[i]-f[i][j-1]};
		for(int i=2;i<=n;++i)
		{
			Node u=(Node){i,s[i]};
			while(H<T&&Slope(u,q[Q[H]])<Slope(u,q[Q[H+1]]))++H;
			zy[i][j]=Q[H];f[i][j]=(s[i]-s[Q[H]]+f[Q[H]][j-1])/(i-Q[H]+1);
			while(H<T&&Slope(q[Q[T]],q[Q[T-1]])>Slope(q[Q[T]],q[i]))--T;
			Q[++T]=i;
		}
	}
	int m=n-K+lim,pos;double mx=0;
	for(int j=0;j<=lim;++j)
		if(f[m][j]>mx)mx=f[m][j],pos=j;
	ans=Calc(m,pos);
	for(int i=m+1;i<=n;++i)ans=(ans+h[i])/2;
	cout<<ans.to_string(p<<1)<<endl;
	return 0;
}