讨论/题目交流/🏆 第 180 场力扣周赛/
🏆 第 180 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 矩阵中的幸运数
4 分 - 设计一个支持增量操作的栈
4 分 - 将二叉搜索树变平衡
6 分 - 最大的团队表现值

最后一道题被取模误导了, 太坑爹了. 还好最后机智地发现了它就是想误导我, 然后顺利做出来了, 哈哈.

最后一题做法:
由于要每次乘以效率最小的, 因此我们可以按照每个人效率进行升序排序. 排序之后你可以发现, 第i个人后面的人效率都比它大, 所以如果选k个人(包括i的话), 那么就是它后面人里挑k-1个speed最大的,不用再管efficient了. 怎么挑k-1个最大的呢? 小顶堆啊! capacity限制为k. 同时维护一个堆的total值避免每次去计算. 所以就是先对efficient排序, 然后倒序枚举, 同时维护堆. 数据范围一你算发现int64存得下, 狗日的, 害得我写了半天高精度...

最终:

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn max_performance(n: i32, speed: Vec<i32>, efficiency: Vec<i32>, k: i32) -> i32 {
        const M: i64 = 1000000007;
        // Vec<(效率, 速度)>
        let mut tuple: Vec<(i32, i32)> = efficiency.into_iter().zip(speed).map(|t| t).collect();
        tuple.sort_by(|a,b| {
            if a.0 == b.0 { // 按efficient排序, 相同的则按speed排序
                return a.1.cmp(&b.1);
            }
            a.0.cmp(&b.0)
        });
        let uk = k as usize;
        let mut heap = BinaryHeap::new();
        let mut total = 0;
        let n = n as usize;
        let mut ans = 0;
        for i in (n-uk..n).rev() { // 枚举最后k个, 因为题目是最多k, 可以小于k
            heap.push(Reverse(tuple[i].1 as i64));
            total += tuple[i].1 as i64;
            ans = ans.max(tuple[i].0 as i64 * total);
        }
        for i in (0..n-uk).rev() {
            let peek = heap.peek().unwrap_or(&Reverse(0)).0; // 取堆顶值, 也就是k个数中的最小值
            let maybe_new_total = total+tuple[i].1 as i64-peek; // 由于要把当前这个人选中, 而又要选k个人, 因此就需要把堆中speed最小那个人排除,加上当前这个人的speed
            let cur = tuple[i].0 as i64 * maybe_new_total;
            ans = ans.max(cur);
            if tuple[i].1 as i64 > peek { // 如果当前人的speed大于堆的最小值, 那么就更新堆
                heap.pop();
                heap.push(Reverse(tuple[i].1 as i64));
                total = maybe_new_total;
            }
        }
        (ans % M) as i32
    }
}
4
展开全部 31 讨论