首页 > 试题广场 >

礼物

[编程题]礼物

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

“呼！！佳慧，我拿到面试直通卡了！”“吓死宝宝了！哦，你拿到直通卡了啊，好哒，进去吧，你可以直接接受老大的面试了”。
亮亮来到老大的办公室，“骚年，你想做什么工作啊？”“我要做大数据分析！！”
“哦~~那你先帮我们解决一个问题。是这样的，我们这次招聘会一共有N个人，我们公司给大家准备了一些礼物，但是我们并不知道这些人具体喜欢什么，现在库房共有m种礼物，每种礼物有Ci件，共N件。而我们大致知道每个人选择某种礼物的概率，即能知道Pij(编号为i的人选择第j种礼物的概率)。现在所有人按编号依次领礼物（第1个人先领，第N个人最后领），领礼物时，参加者会按照预先统计的概率告诉准备者自己想要哪一种礼物，如果该种礼物在他之前已经发放完了则他会领不到礼物，请帮我们计算出能能领到礼物的期望人数。

输入描述:

第一行包含两个整数N(1≤N≤300),M(1≤M≤100)，用单个空格隔开。表示公有N个应聘者，M种礼物。
第二行为M个整数，依次为C_i，第i种礼物的个数。
接下来的N行，每行M个实数，一次为P_ij，第i个人选择第j种礼物的概率。

输出描述:

一行输出期望人数。结果保留1位小数。

示例1

输入

输出

1.6(样例解释：共有4种选择(1,1),(1,2),(2,1),(2,2)，概率分别为0.21、0.09、0.49、0.21，(1,1),(2,2)这两种选择只有1个人能拿到礼物，(1,2),(2,1)这两种选择有2个人能拿到礼物，所以期望为1*(0.21+0.21) + 2*(0.09+0.49) = 1.58，保留一位小数为1.6。)

算法知识视频讲解

Java

倚栏听风兼听雨

import java.util.;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
while(s.hasNext()) {
int n = s.nextInt(); //人数
int m = s.nextInt(); //礼物种类数
int[] gnum = new int[m]; //每类礼物个数
for(int i=0; i<m; i++) {
gnum[i] = s.nextInt();
}
float[][] chance = new float[n][m]; //每个人选择每种礼物概率
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
chance[i][j] = s.nextFloat();
}
}
double leftgift = 0; //余下礼物数
//对每类礼物进行循环
for(int i=0; i<m; i++) {
if(gnum[i]==0)
continue;
double[] leftpro = new double[gnum[i]+1]; //此类礼物不同剩余个数(0-gnum[i])的概率
leftpro[gnum[i]] = 1; //初始化为都在
//在每个人选择后对概率进行调整
for(int j=0; j<n; j++) {
leftpro[0] = leftpro[0] + leftpro[1]chance[j][i];
for(int k = 1; k<gnum[i]; k++) {
leftpro[k] = leftpro[k](1-chance[j][i]) + leftpro[k+1]chance[j][i];
}
leftpro[gnum[i]] = leftpro[gnum[i]] (1-chance[j][i]);
}
for(int j=1; j<=gnum[i]; j++) {
leftgift += leftpro[j] j;
}
}
System.out.println((double) (Math.round((n - leftgift)*10)/10.0));
}
s.close();
}
}