[二分][假·数论]分数

题目描述

nput
第一行包含两个正整数N和P，表示选手的个数以及精度要求。
接下来的N行，每行包含一个0到100（闭区间）内的整数。

Output
输出一个实数，取P位有效数字，下取整。

Sample Input
5 4
100
20
15
10
8

Sample Output
195.2

Data Constraint
一共有10个测试点，P的值依次是1到10。
对100%的数据，N≤20

分析

从上方的提示图可以得知这是一个下凹的曲线，符合三分性质
但是老子就是不打三分，咋地
设难度为h，区分度为d，每个选手实力为xi，理想分数为ai.
令yi=h-d*xi
分数偏差值F(h,d)可化简为
F(h,d)=sigma{ ai*ln(1+e^yi) + (100-ai)*ln(1+e^(-yi)) }
分别求出F(h,d)关于h和d的导数:
Fh’=sigma{ ai-100/(1+e^yi) }
Fd’=sigma{ xi*(100/(1+e^yi)-ai) }
容易发现Fh’,Fd’单调递增.
可以首先二分d，对于确定的d=d’，二分解出Fh’=0的零点h’，若Fd’<0，令d的下界为d’，否则令d的上界为d’.
自行理解吧，把数学部分去掉还是很容易的（就是考数学好吗？）
然鹅我没有学过微积分所以GG咯，看公式好了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for (i=a;i<=b;i++)
const int N=21;
const double eps=1e-11;
using namespace std;
int n,p;
int a[N];
double x[N];
bool Cmp(int a,int b) {
    return a>b;
}
int main() {
    int i;
    scanf("%d%d",&n,&p);
    rep(i,1,n) {
        scanf("%d",&a[i]);
        x[i]=100.0/(n-1)*(n-i);
    }
    sort(a+1,a+n+1,Cmp);
    double dl=0.0,dr=2000.0,dmid,hl,hr,hmid;
    while (dl+eps<dr) {
        dmid=(dl+dr)*0.5;
        hl=0.0;hr=2000.0;
        while (hl+eps<hr) {
            hmid=(hl+hr)*0.5;
            double fh=0;
            rep(i,1,n)
            fh+=x[i]-100.0/(1.0+exp(hmid-dmid*a[i]));
            if (fh<0) hl=hmid; else hr=hmid;
        }
        double fd=0;
        rep(i,1,n)
        fd+=a[i]*(100.0/(1.0+exp(hmid-dmid*a[i]))-x[i]);
        if (fd<0) dl=dmid; else dr=dmid;
    }
    double least=0.0;
    rep(i,1,n)
    least+=(x[i]*log(1.0+exp(hmid-dmid*a[i]))+(100.0-x[i])*log(1.0+exp(dmid*a[i]-hmid)));
    char strleast[20]="";
    bool b=0;
    sprintf(strleast,"%.10lf",least);
    int len=strlen(strleast);
    rep(i,0,p-1) {
        if (strleast[i]=='.') {
            b=1;
            printf(".");
        }
        printf("%c",strleast[i+b]);
    }
    i--;
    if (!b)
    while (++i<=len&&strleast[i]!='.')
    printf("0");
}