2022-11-22：小美将要期中考试，有 n 道题，对于第 i 道题，小美有 pi 的几率做对，获得 ai 的分值，还有 (1-pi) 的概率做错，得 0 分。小美总分是每道题获得的分数。小美不甘于此，决定突击复习，

2022-11-22
北京
本文字数：689 字
阅读完需：约 2 分钟

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;}