题意：有$n$个人，对每个人，他有$p_i$的概率饥饿值为$x_i$（$1\leq i\leq m$），你现在要做$n$盘寿司，每盘寿司有一定的数量，当这$n$个人的饥饿值确定后他们会自己选择最优的（人，寿司）配对方案使得$C=\sum\limits_{i=1}^n\left\lvert h_i-c_i\right\rvert$最小（设第$i$个人饥饿值为$h_i$，吃的寿司数量为$c_i$），现在要合适地选择$c_{1\cdots n}$使得$C$的期望最小，输出这个最小的期望
首先，如果确定了$h_{1\cdots n},c_{1\cdots n}$，那么将它们都排序就可以得到最小的$C$，因为如果先把$h$从小到大排序，并且存在$c_i\gt c_j$，那么交换$c_i,c_j$不会让$C$变大
那么我们要最小化$\sum\limits_{i=1}^n\sum\limits_{j=1}^mt_{i,j}\left\lvert c_i-x_j\right\rvert$，其中$t_{i,j}$为这些随机变量中第$i$小的数是$x_j$的概率
设$u_{i,j}$为第$i$小的数$\leq x_j$的概率，那么$t_{i,j}=u_{i,j}-u_{i,j-1}$，我们要算$u$
设$s$为$p$的前缀和，因为恰有$k$个数$\leq x_j$的概率为$\binom nks_j^k(1-s_j)^{n-k}$，所以$u_{i,j}=\sum\limits_{k=i}^n\binom nks_j^k(1-s_j)^{n-k}$
最后的问题是要确定$c_i$使得$\sum\limits_{i=1}^n\sum\limits_{j=1}^mt_{i,j}\left\lvert c_i-x_j\right\rvert$最小，对每个$i$分开考虑，就是求一条折线上的最小值，而折线上的最小值只能在端点处取到，所以扫一遍即可
#include<stdio.h>
typedef long double du;
const du inf=9223372036854775807.;
void fmin(du&a,du b){
if(b<a)a=b;
}
du pow(du a,int b){
du s=1;
for(;b;b>>=1){
if(b&1)s*=a;
a*=a;
}
return s;
}
int x[2010],m;
du s[2010],c[2010][2010],t[2010][2010],st[2010];
du solve(du*t){
int i;
du res;
for(i=1;i<=m;i++){
st[i]=st[i-1]+t[i];
s[i]=s[i-1]+t[i]*x[i];
}
res=inf;
for(i=1;i<=m;i++)fmin(res,st[i]*x[i]-s[i]+s[m]-s[i]-(st[m]-st[i])*x[i]);
return res;
}
int main(){
int n,Q,i,j;
du res;
scanf("%d%d%d",&n,&m,&Q);
for(i=1;i<=m;i++){
scanf("%d%d",x+i,&j);
s[i]=s[i-1]+j/(du)Q;
}
c[0][0]=1;
for(i=1;i<=n;i++){
c[i][0]=1;
for(j=1;j<=i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j];
}
for(i=n;i>0;i--){
for(j=1;j<=m;j++)t[i][j]=t[i+1][j]+c[n][i]*pow(s[j],i)*pow(1-s[j],n-i);
}
res=0;
for(i=1;i<=n;i++){
for(j=m;j>0;j--)t[i][j]-=t[i][j-1];
res+=solve(t[i]);
}
printf("%.8lf",(double)res);
}