Re: [閒聊] 每日leetcode

[yam276 (虛構史學家)]

※ 引述《DJYOSHITAKA (franchouchouISBEST)》之銘言：
: 502. IPO
: 維持maxheap內只有符合capital條件的profits即可

思路:

Rust有MaxHeap

建立一個可用項目MaxHeap

每次把最大利潤加入資本並移出Heap

然後判斷有沒有新項目可以加入MaxHeap


Code:

use std::collections::BinaryHeap;

impl Solution {
    pub fn find_maximized_capital(
        k: i32,
        mut w: i32,
        profits: Vec<i32>,
        capital: Vec<i32>,
    ) -> i32 {
        let mut available_items = BinaryHeap::new();
        let mut not_available_items: Vec<(i32, i32)> =
                capital.into_iter().zip(profits.into_iter()).collect();

        not_available_items.sort_unstable_by_key(|&(c, _)| c);

        let mut i = 0;
        for _ in 0..k {
            while i < not_available_items.len() &&
                  not_available_items[i].0 <= w {
                available_items.push(not_available_items[i].1);
                i += 1;
            }

            if let Some(max_profit) = available_items.pop() {
                w += max_profit;
            } else {
                break;
            }
        }

        w
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718423112.A.132.html
推 JIWP: 別卷了