2022-06-15：薯队长最近在参加了一个活动，主办方提供了N个礼物以供挑选，每个礼物有一个价值，范围在0 ~ 10^9之间，

福大大架构师每日一题

发布于 2023-06-08 14:32:59

1390

发布于 2023-06-08 14:32:59

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

执行结果如下：