http://www.lydsy.com/JudgeOnline/problem.php?id=3330
下面画了那么一大幅图告诉你是单峰函数,再说随便几组数据也能验证是不是单峰嘛。赶紧套三分
呜~代码能力太渣了,有效数字写那么久
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive Blog:http://willinglive.cf ************************************************/ #define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) inline const int read() {int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1; for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;} ///////////////////////////////////////////////// int n,p; int a[22]; double b[22]; double eps=1; ///////////////////////////////////////////////// double cal3(double k,double d) { double res=0; rep(i,1,n) { double s=100/(1+exp(k-d*a[i])); if(s<1e-12 || s>=100) return 1e200; res+=b[i]*log(100/s) + (100-b[i])*log(100/(100-s)); } return res; } double cal2(double k) { double l=0,r=1,mid1,mid2,ret1,ret2; while(r-l>eps) { mid1=(l+r)/2; mid2=(mid1+r)/2; ret1=cal3(k,mid1); ret2=cal3(k,mid2); if(ret1>ret2) l=mid1; else r=mid2; } return cal3(k,(l+r)/2); } double cal1() { double l=0,r=10,mid1,mid2,ret1,ret2; while(r-l>eps) { mid1=(l+r)/2; mid2=(mid1+r)/2; ret1=cal2(mid1); ret2=cal2(mid2); if(ret1>ret2) l=mid1; else r=mid2; } return cal2((l+r)/2); } double print(double ans) { LL a=(LL)ans; int digit=0; for(int tmp=a;tmp;tmp/=10) digit++; if(p<=digit) { int bit[100]; for(*bit=0;a;a/=10) bit[++*bit]=a%10; for(int i=*bit;i>=1 && p;i--,digit--,p--) { putchar(bit[i]+'0'); } while(digit--) putchar('0'); } else { cout<<a<<'.'; p-=digit; while(p--) ans-=(int)ans,ans*=10,printf("%d",(int)ans); } } ///////////////////////////////////////////////// void input() { cin>>n>>p; rep(i,1,n) a[i]=read(); rep(i,1,n) eps/=10; sort(&a[1],&a[n+1]); } void solve() { rep(i,1,n) b[i]=(i-1)*100.0/(n-1); double ans=cal1(); print(ans);//SXBK!!!!!!!!! } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("score.in","r",stdin); freopen("score.out","w",stdout); #endif input(),solve(); return 0; }