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<i32> = vec![6, 19, 3, 8, 29];
    let ans = max_near(&mut nums, 3);
    println!("ans = {}", ans);
}

fn max_near(arr: &mut Vec<i32>, 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<i32>, 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代码