首页 > 试题广场 >

排队吃饭

[编程题]排队吃饭

热度指数：88 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

牛牛所在的学校有 $n$ 个学生.并且学校里面有 $m$ 个食堂,因为每个食堂里面有多个取餐点,所以我们描述第 $i$ 个食堂里面有 $a_i$ 个窗口可以排队取餐.在吃午饭的时候,每个学生都会等概率的选择一个食堂就餐.而且一个食堂内的学生在排队取餐的过程中,他们都会倾向于使最长的队伍尽可能的短,现在牛牛请你帮他计算出所有食堂内最长队伍长度的期望.

输入描述:

第一行输入两个正整数 $n$ 和 $m$ .
第二行输入 $m$ 个整数 $a_i$ .
$1\leq m,n \leq 50$

$1\le a_i \le n$

输出描述:

输出一个小数表示长度期望.在<1e-8范围内都视为正确输出.

示例1

输入

5 5
5 5 5 5 5

输出

1.0000000000

说明

示例2

输入

2 4
1 1 1 1

输出

1.2500000000

示例3

输入

2 2
1 1

输出

1.5000000000

算法知识视频讲解

GreyPigeon

// copy 别人的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int a[56];
double dp[56][56][56];
double C[56][56];

int main()
{
	cin>>n>>m;
	C[0][0] = 1.0;
	for(int i=1;i<=55;i++)
	{
		C[i][0] = 1.0;
		for(int j=1;j<=i;j++)
		{
			C[i][j] = (i-j+1)*C[i][j-1]/j;
		}
	}
	for(int i=1;i<=m;i++) cin>>a[i];
	for(int i=0;i<=n;i++) dp[0][0][i] = i;
	
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
				for(int c=0;c<=j;c++)
				{
					int Max = max(k,(c+a[i]-1)/a[i]);
					dp[i][j][k] += dp[i-1][j-c][Max] * pow(i-1,j-c) / pow(i,j) * C[j][c];
				}
			}
		}
	}
	printf("%.10f\n",dp[m][n][0]);
	return 0;
}

发表于 2022-07-25 18:25:40 回复(0)