noi的题你就这么水...
by mengbierr @ 2017-08-21 15:17:58
@[无敌](/space/show?uid=35873) 怎么了，我除了水并不会其他算法……
by yltx @ 2017-08-21 15:30:27
@[一思千年](/space/show?uid=50649) 额，这题有个高精度模板，而且复杂度也不对
by mengbierr @ 2017-08-21 17:03:02
@[无敌](/space/show?uid=35873) [然而……](https://www.luogu.org/record/show?rid=3073341)
by yltx @ 2017-08-22 15:12:10
???
by mengbierr @ 2017-08-22 15:46:02
这里有高精度模板<http://uoj.ac/problem/223>
by mengbierr @ 2017-08-22 15:49:10
http://uoj.ac/problem/223
by mengbierr @ 2017-08-22 15:49:37
@[无敌](/space/show?uid=35873) 那个，数据很烂，我水了61分
by yltx @ 2017-08-23 14:19:21
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define IL inline
#define PC 1.2
#define N 8010
#define REP(a,b,c) for(a=b;a<=c;a++)
#define PER(a,b,c) for(a=b;a<=c;a++)
using namespace std;
typedef long long lol;
const int K=15,bs=1000000000;
//worship PICKS!
int n,k,p,h[N],s[N],x[N],per[K+1][N],ot;
double f[K+1][N],y[N],val[N],y0,x0,k0,k1;
IL int rd(){
int res=0;char c=getchar();while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();return res;
}
struct nd{
int a,b[int(N*PC/9)];
IL void init(){a=0,memset(b,0,sizeof(b));}
IL void operator += (const nd &B){
int i;PER(i,p,1){b[i]+=B.b[i];if(b[i]>=bs)b[i]-=bs,b[i-1]++;}
b[0]+=B.b[0];if(b[0]>=bs)b[0]-=bs,a++;a+=B.a;
}
IL void operator /= (const int d){
int i;lol tmp=b[0]+a%d*1LL*bs;a/=d;
REP(i,0,p)b[i]=tmp/d,tmp=b[i+1]+tmp%d*1LL*bs;
}
};
IL nd solve(int u,int step){
nd rep;
if(!per[step][u]){rep.init();rep.a=h[1];return rep;}
else{
rep=solve(per[step][u],step-1);
if(per[step][u]==u)return rep;
else{
rep.a+=s[u]-s[per[step][u]];
rep/=(u-per[step][u]+1);
return rep;
}
}
}
int main(){
n=rd(),k=rd(),ot=rd(),p=((ot*PC)+8)/9;int i,j,*P;double *F,*G;
h[1]=rd();
REP(i,2,n)if((h[i]=rd())<=h[1])i--,n--;
k=min(k,n);int rnd=min(k,K);
sort(h+2,h+n+1);
REP(i,1,n)s[i]=s[i-1]+h[i];F=f[0];
REP(i,1,n)F[i]=h[1];REP(i,0,rnd)f[i][1]=h[1];
REP(j,1,rnd){
G=F,F=f[j],P=per[j];
int fr=1,tp=0;
x[++tp]=0,y[tp]=s[1]-G[1];
REP(i,2,n){
val[fr]=(s[i]-y[fr])/(i-x[fr]);
while(fr<tp){
val[fr+1]=(s[i]-y[fr+1])/(i-x[fr+1]);
if(val[fr]<val[fr+1])fr++;else break;
}
if(val[fr]>G[i]){
F[i]=val[fr],P[i]=x[fr]+1;
}else{
F[i]=G[i],P[i]=i;
}
x0=i-1,y0=s[i]-G[i];
while(fr<tp){
k0=(y0-y[tp-1])/(x0-x[tp-1]);
k1=(y[tp]-y[tp-1])/(x[tp]-x[tp-1]);
if(k0>k1)break;
tp--;
}
x[++tp]=x0,y[tp]=y0;
}
}
int v=n-max(0,k-rnd);nd ans=solve(v,rnd);
REP(i,v+1,n)ans.a+=h[i],ans/=2;
printf("%d.",ans.a);
if(ot<5)printf("%06d",ans.b[0]/1000);
else REP(i,0,p-1)printf("%09d",ans.b[i]);
return 0;
}
```
by 我很辣ji看签名 @ 2017-11-26 16:58:40