5
16
2016
0

[BZOJ3330] [BeiJing2013]分数

感觉自己三分姿势一直是错的所以来补这题

注意输出就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=25;
const double eps=1e-12,INF=1e200;

int n,p,Bit[N*4];
double a[N],b[N];

void Print(double x){
long long ans=(long long)x;
int dig=0;
while(ans){dig++;Bit[dig]=ans%10;ans/=10;}
ans=(long long)x;
if(dig>=p){
	for(int i=dig;i>=dig-p+1;i--)putchar(Bit[i]+'0');
	for(int i=dig-p;i>=1;i--)putchar('0');
}
else {
	printf("%lld.",ans);
	x-=ans;
	p-=dig;
	while(p--){x*=10;putchar(((long long)x)%10+'0');}
}
putchar('\n');
}

double Score(int x,double diff,double disc){
return 100.0/(1.0+exp(diff-disc*a[x]));
}

double Dec(double diff,double disc){
double ans=0.0;
for(int i=1;i<=n;i++){
    double Sc=Score(i,diff,disc);
    if(Sc<eps || Sc+eps>=100.0)return INF;
    ans+=b[i]*log(100.0/Sc)+(100.0-b[i])*log(100.0/(100.0-Sc));
}
return ans;
}

double Div3_2(double diff){
double l=0.0,r=1.0;
while(r-l>eps){
	double mid1=(l+r)/2,mid2=(mid1+r)/2;
	if(Dec(diff,mid1)>Dec(diff,mid2))l=mid1;
	else r=mid2;
}
return Dec(diff,(l+r)/2);
}

void Div3(){
double l=0.0,r=10.0;
while(r-l>eps){
	double mid1=(l+r)/2,mid2=(mid1+r)/2;
	if(Div3_2(mid1)>Div3_2(mid2))l=mid1;
	else r=mid2;
}
Print(Div3_2((l+r)/2));
}

int main(){
freopen("3330.in","r",stdin);
freopen("3330.out","w",stdout);
scanf("%d %d",&n,&p);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)b[i]=100.0*(i-1)/(n-1);
Div3();
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 458

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com