[Hackerrank题目选做] Random Number Generator 二分+数学+猜结论

题目链接: https://www.hackerrank.com/challenges/random-number-generator-1

题解: 假设1-N产生的概率分别为p[1],....p[N]，

          则期望得分为sigma(i=1....n,j=i....n,p[i]*p[j]*(i+j))-sigma(i=1....n,p[i]*p[i]*2*i).

          看到这个式子，菜鸡博主可能没有什么高超的数学姿势啊，于是开始强推------>好像并没有什么卵用，

          然而因为太菜，博主并没有想到把期望得分的计算拆开来看考虑每个数的贡献(还是万能的UOJ群的某大牛讲的)

          于是考虑每个数字对于答案的贡献，则期望得分可以写成sigma(i=1...n,2*i*p[i]*(1-p[i])).

          这个式子中，2是常数扔掉，需要最大化的式子就变成了sigma(i=1...n,i*p[i]*(1-p[i])).

          而显然的是，为了使这个式子的值最大化，p[i]*(1-p[i])的值显然单调不下降，同时，任何pi的值都不会大于0.5.

          根据这个性质，考虑分析样例法---->

                                     样例为N=3，最优情况下: p[1]=5/22,p[2]=4/11,p[3]=9/22.

                                     然后如果与1/2做差，就会发现三个数的比值为6:3:2，也就是1：(1/2)：(1/3)

          大胆猜想，1-N所有数字概率与1/2做差后的比为1：(1/2)：(1/3)：.....：(1/N).

          然后就能得到方程：sigma(0.5-(1/i)*X)=1.

          令har[i]=1+1/2+.....+1/N，

          转化后就可以得到：0.5*N-har[N]*X=1

         从而可以解出X=(0.5N-1)/har[N].

         但是这么做是错误的，因为代入后会惊奇地发现前面数字的概率变成了负数，

         所以二分一个位置，使这个位置之前的数字全为0，后面再按比值来计算，使得没有概率是负数，

         对于mid位置，sigma(i=mid...N,0.5-(1/i)*X)=1，

         可化为(N-mid+1)*0.5-X*(har[N]-har[mid-1])=1------>X=((N-mid+1)*0.5-1)/(har[N]-har[mid-1]).

         求出X后，计算出p[mid]=0.5-(1/mid)*X，

         比较它与0的大小以进行判断。

         然后再按照上面所提到的方法给每个数以一个概率，从而使最终的答案最大化(其实这么做是O(TN)的，但是能过)，

         后面这部分也可以通过推式子做到O(1)，可是我不会，知道的大牛可以讲一讲啊。

         ZZT神犇说了，这个东西可以拉格朗日乘数法解决，菜鸡表示完全不懂

Code:

#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
double har[1000005],p[1000005];
int main (){
	int i,n,test;
	for (i=1;i<=1000000;i++)
	{har[i]=har[i-1]+(1.0/((double)(i)));}
	scanf ("%d",&test);
	while (test--)
	{scanf ("%d",&n);
	if (n==1) {printf ("0.00000000\n");continue;}
	if (n==2) {printf ("0.50000000\n");continue;}
	int lc=1,rc=n;
	while (lc<=rc)
	{int mid=(lc+rc)>>1;
	double x=(((double)(n-mid+1))*0.5-1.0)/(har[n]-har[mid-1]);
	double del=0.5-(1.0/((double)(mid)))*x;
	if (del<-eps) {lc=mid+1;}
	else {rc=mid-1;}
	}
	double x=(((double)(n-lc+1))*0.5-1.0)/(har[n]-har[lc-1]);
	double ans=0;
	for (i=lc;i<=n;i++)
	{p[i]=0.5-(1.0/((double)(i)))*x;
	ans+=(((double)(i))*p[i]*(1.0-p[i])*2);
	}
	ans/=((double)(2*n-1));
	printf ("%.12lf\n",ans);
	}
	return 0;
}