首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-11-22:小美将要期中考试,有n道题,对于第i道题, 小美有pi的几率做对,获得ai的分值,还有(1-pi)的概率做错,得0分。 小美总分是每道题获

2022-11-22:小美将要期中考试,有n道题,对于第i道题, 小美有pi的几率做对,获得ai的分值,还有(1-pi)的概率做错,得0分。 小美总分是每道题获

原创
作者头像
福大大架构师每日一题
发布2022-11-22 22:18:13
2100
发布2022-11-22 22:18:13
举报

2022-11-22:小美将要期中考试,有n道题,对于第i道题,

小美有pi的几率做对,获得ai的分值,还有(1-pi)的概率做错,得0分。

小美总分是每道题获得的分数。

小美不甘于此,决定突击复习,因为时间有限,她最多复习m道题,复习后的试题正确率为100%。

如果以最佳方式复习,能获得期望最大总分是多少?

输入n、m

接下来输入n个整数,代表pi%,为了简单期间,将概率扩大了100倍。

接下来输入n个整数,代表ai,某道题的分值

输出最大期望分值,精确到小数点后2位

数据 1m<=n<=50000

来自美团。8.20笔试。题目1。

答案2022-11-22:

丢掉的分数的期望排序。复习前m道题。

代码用rust编写。代码如下:

use std::iter::repeat;

fn main() {
    let mut pi = vec![20, 50];
    let mut ai = vec![100, 200];
    let ans = maximum_expected_score(&mut pi, &mut ai, 1);
    println!("ans = {:?}", ans);
}

fn maximum_expected_score(pi: &mut Vec<i32>, ai: &mut Vec<i32>, m: i32) -> f64 {
    let n = pi.len() as i32;
    //不复习的分数总和
    let mut not_review_score = 0;
    //复习的获得分数数组
    let mut review_vec: Vec<i32> = repeat(0).take(n as usize).collect();
    for i in 0..n {
        not_review_score += ai[i as usize] * pi[i as usize];
        review_vec[i as usize] = ai[i as usize] * (100 - pi[i as usize]);
    }
    //对复习数组排序
    review_vec.sort();
    review_vec.reverse();
    let mut ans = not_review_score;
    for i in 0..m {
        ans += review_vec[i as usize];
    }
    return ans as f64 / 100.0;
}

执行结果如下:

在这里插入图片描述
在这里插入图片描述

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档