2023.6.7 老鼠和奶酪

发布时间 2023-06-07 12:54:03作者: 烤肉kr

image

贪心+排序。

由于第一只老鼠一定要吃k个奶酪的,为了让答案最大,一定要吃k个收益最大的奶酪。而reward1reward2大的越多,收益就越多。所有可以按照reward1 - reward2进行从大到小的排序,排完序后前k个奶酪由第一个老鼠吃,后面的所有奶酪由第二个老鼠吃,得到的就是最大得分。

use std::cmp::Ordering;

impl Solution 
{
    pub fn mice_and_cheese(reward1: Vec<i32>, reward2: Vec<i32>, k: i32) -> i32 
    {
        let mut rewards:Vec<_> = reward1.into_iter().zip(reward2.into_iter()).collect();
        rewards.sort_unstable_by(|&a, &b| if a.0 - b.0 < a.1 - b.1 { Ordering::Greater } else { Ordering::Less });
    	let mut res = 0;
    	rewards.iter().enumerate().for_each(|(i, &(x, y))| if i < k as usize { res += x } else { res += y });
    	res
    }
}