Manthan, Codefest 16 E. Startup Funding ST表 二分 数学
E. Startup Funding
题目连接：
http://codeforces.com/contest/633/problem/E
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。Description
An e-commerce startup pitches to the investors to get funding. They have been functional for n weeks now and also have a website!
For each week they know the number of unique visitors during this week vi and the revenue ci. To evaluate the potential of the startup at some range of weeks from l to r inclusive investors use the minimum among the maximum number of visitors multiplied by 100 and the minimum revenue during this period, that is:
The truth is that investors have no idea how to efficiently evaluate the startup, so they are going to pick some k random distinct weeks li and give them to managers of the startup. For each li they should pick some ri ≥ li and report maximum number of visitors and minimum revenue during this period.
Then, investors will calculate the potential of the startup for each of these ranges and take minimum value of p(li, ri) as the total evaluation grade of the startup. Assuming that managers of the startup always report the optimal values of ri for some particular li, i.e., the value such that the resulting grade of the startup is maximized, what is the expected resulting grade of the startup?
Input
The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 1 000 000).
The second line contains n integers vi ( ) — the number of unique visitors during each week.
The third line contains n integers ci ( ) —the revenue for each week.
Output
Print a single real value — the expected grade of the startup. Your answer will be considered correct if its absolute or relative error does not exceed .
Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .
Sample Input
3 2
3 2 1
300 200 300
Sample Output
133.3333333
Hint
题意
有n个人，每个人有两个权值，v[i]和c[i]
然后有一个函数p(l,r) = min(100max(v[l..r]),min(c[l..r]))
对于每一个i，你需要找到一个最大的p(i,ri)
然后现在从n个p(i,ri)中选取k个，然后再从这k个中选取其中最小的
问你选出来的数的期望是多少
题解：
这个题目很明显分成了两个部分：
１．求val[i] (即最大p(i,ri))
２．求期望
step1:
我们先来讨论第一个问题，对于位置i,
令 令 令
那么 单 增 ， 单 减 ，想象一下两条直线一个单增，一个单减，那么存在一个交点，这个意思就是说 很 明 显 是 先 单 增 再 单 减 ，直接二分求交点即可。但是我发现可以不用二分，嘿嘿。
因为我发现 ,不难发现从i到i+1,交点只会往后移动，这个自己画个图就很清晰啦，画图能使问题变得直观简单。
讲到这还不会建议你自己想想，因为看一半题解，再想一半这样效果更好。
step2:
这个就是一个组合数学的问题，只要有一点基础都可以推出来（因为连我都推出来了）
先将val从小到大排序，答案就是 。但是这样是不是太大了，所以我们要用递推求。
令 ,不难推出来
这样我们就做完啦。
代码
xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000050
int n,k,a[N],b[N],val[N],mx[N][21],mi[N][21],mm[N];
template<typename T>void read(T&x)
{
ll k=0; char c=getchar();
x=0;
while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
if (c==EOF)exit(0);
while(isdigit(c))x=x10+c-'0',c=getchar();
x=k?-x:x;
}
void read_char(char &c)
{while(!isalpha(c=getchar())&&c!=EOF);}
void init_ST(int n)
{
mm[0]=-1;
for(int i=1;i<=n;i++)
{
mx[i][0]=a[i];
mi[i][0]=b[i];
mm[i]=(i&(i-1))==0?mm[i-1]+1:mm[i-1];
}
for(int i=1;i<=20;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
{
mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
}
}
int compare(int x,int y)
{
if (x>y)swap(x,y);
int k=mm[y-x+1],a1,a2;
a1=max(mx[x][k],mx[y-(1<<k)+1][k]);
a2=min(mi[x][k],mi[y-(1<<k)+1][k]);
return a1-a2;
}
int get_p(int x,int y)
{
if (y>n)return 0;
if (x>y)swap(x,y);
int k=mm[y-x+1],a1,a2;
a1=max(mx[x][k],mx[y-(1<<k)+1][k]);
a2=min(mi[x][k],mi[y-(1<<k)+1][k]);
return min(a1,a2);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("aa.in","r",stdin);
#endif
read(n); read(k);
for(int i=1;i<=n;i++)read(a[i]),a[i]=100;
for(int i=1;i<=n;i++)read(b[i]);
init_ST(n);
int r=0;
for(int i=1;i<=n;i++)
{
r=max(r,i);
while(r+1<=n&&compare(i,r+1)<=0)r++;
val[i]=max(get_p(i,r),get_p(i,r+1));
}
sort(val+1,val+n+1);
double ans=0,f2,f1=k1.0/(n-k+1);
for(int i=1;i<=n;i++)
{
f2=f1(n-k-i+2)1.0/(n-i+1);
ans+=f2val[i];
f1=f2;
}
printf("%.7lf",ans);
}
