栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

2022-06-15:薯队长最近在参加了一个活动,主办方提供了N个礼物以供挑选, 每个礼物有一个价值,范围在0 ~ 10^9之间, 薯队长可以从中挑选k个礼物。 返回:其中价值最接近的两件礼物之间相差

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

2022-06-15:薯队长最近在参加了一个活动,主办方提供了N个礼物以供挑选, 每个礼物有一个价值,范围在0 ~ 10^9之间, 薯队长可以从中挑选k个礼物。 返回:其中价值最接近的两件礼物之间相差

2022-06-15:薯队长最近在参加了一个活动,主办方提供了N个礼物以供挑选,
每个礼物有一个价值,范围在0 ~ 10^9之间,
薯队长可以从中挑选k个礼物。
返回:其中价值最接近的两件礼物之间相差值尽可能大的结果。
小红书第二题。

薯队长最近在玩一个游戏,这个游戏桌上会有一排不同颜色的方块,
每次薯队长可以选择一个方块,便可以消除这个方块以及和他左右相临的
若干的颜色相同的方块,而每次消除的方块越多,得分越高。
具体来说,桌上有以个方块排成一排 (1 <= N <= 200),
每个方块有一个颜色,用1~N之间的一个整数表示,相同的数宇代表相同的颜色,
每次消除的时候,会把连续的K个相同颜色的方块消除,并得到K*K的分数,
直到所有方块都消除。显然,不同的消除顺序得分不同,薯队长希望您能告诉他,这个游戏最多能得到多少分。
小红书第三题。

答案2022-06-15:

二分答案法。

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

fn main() {
    let mut nums: Vec = vec![6, 19, 3, 8, 29];
    let ans = max_near(&mut nums, 3);
    println!("ans = {}", ans);
}

fn max_near(arr: &mut Vec, k: i32) -> i32 {
    if (arr.len() as i32) < k {
        return -1;
    }
    arr.sort();
    let n = arr.len() as i32;
    let mut l = 0;
    let mut r = arr[(n - 1) as usize] - arr[0];
    let mut m = 0;
    let mut ans = 0;
    while l <= r {
        m = (l + r) / 2;
        if yeah(arr, k, m) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

fn yeah(arr: &mut Vec, k: i32, limit: i32) -> bool {
    let mut last = arr[0];
    let mut pick = 1;
    for i in 1..arr.len() as i32 {
        if arr[i as usize] - last >= limit {
            pick += 1;
            last = arr[i as usize];
        }
    }
    return pick >= k;
}

执行结果如下:


左神java代码

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975274.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号