在 Rust 中，BinaryHeap 默认是最大堆（Max-Heap）， 即堆顶（peek/pop 时获取的元素）始终是当前集合中的最大值。
self_inc.partial_cmp(&other_inc) 本身的比较方向是“从小到大”， 但配合 BinaryHeap（最大堆）使用时，会变成“从大到小”的最终效果！
如果要实现最小堆 --- 将 Ord 比较用 other.partial_cmp(self) 实现..
举例如下
#[derive(Debug, PartialEq)]
struct Class {
pass: i32, // 通过考试的学生人数
total: i32, // 班级总学生人数
}
impl Eq for Class{}
impl PartialOrd for Class {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Class {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
let self_inc = (self.pass as f64 + 1.0) / (self.total as f64 + 1.0) - (self.pass as f64) / (self.total as f64);
let other_inc = (other.pass as f64 + 1.0) / (other.total as f64 + 1.0) - (other.pass as f64) / (other.total as f64);
self_inc.partial_cmp(&other_inc).unwrap_or(std::cmp::Ordering::Equal)
}
}
🔁 矩阵翻转对称路径
for i in 0..n {
for j in 0..i {
let tmp = fruits[i][j];
fruits[i][j] = fruits[j][i];
fruits[j][i] = tmp;
}
}
对于整数 a 和 b（b > 0），向上取整的公式为：
let ceil_div = (a + b - 1) / b;核心：有多个任务，每个任务能做的时间有限，求最多能完成多少个。
🟢 贪心 + 排序 （Reverse 小顶堆）
本质：在不能重叠的区间中选择最多 k 个会议，使得 价值总和最大。
🟢 动态规划 with 二分差找优化
核心套路：
我们定义一个 DP 状态：
dp[i][j] 表示前 i 个会议中，最多选择 j 个会议所能获得的最大价值。
状态转移：
不选第 i 个会议：dp[i][j] = dp[i-1][j]
选第 i 个会议：
找到第 i 个会议之前 最后一个不冲突的会议（结束时间 < 第 i 个会议的开始时间）
然后转移：dp[i][j] = dp[prev][j-1] + value[i]
关键点：
用 二分查找快速找到这个 prev。📚 手写二分模板
// arr = [1, 3, 5, 6, 9]
// target = 6
// 应返回下标 2（arr[2] = 5 是最后一个 < 6 的）
// 查找右边界
fn upper_bound_rightmost_less_than(arr: &[i32], target: i32) -> Option<usize> {
if arr.is_empty() {
return None;
}
let mut left = 0;
let mut right = arr.len() - 1;
while left < right {
let mid = (left + right + 1) / 2;
if arr[mid] < target {
left = mid;
} else {
right = mid - 1; // 向右靠拢
}
}
if arr[left] < target {
Some(left)
} else {
None
}
}
// arr = [1, 3, 5, 6, 9]
// target = 5
// 应返回下标 2（arr[2] = 5 是第一个 >= 5 的）
// 差找左边界
fn lower_bound_first_ge(arr: &[i32], target: i32) -> Option<usize> {
if arr.is_empty() {
return None;
}
let mut left = 0;
let mut right = arr.len(); // 注意这里是 arr.len()
while left < right {
let mid = (left + right) / 2;
if arr[mid] < target {
left = mid + 1; // 向左靠拢.
} else {
right = mid;
}
}
if left < arr.len() && arr[left] >= target {
Some(left)
} else {
None
}
}
// 返回的 left = 3， 6
fn lower_2(arr: &[i32], target: i32){
let mut left = 0;
let mut right = arr .len();
while left < right {
let mid = left + (right - left) / 2;
// 最终
// <= 是第一个大于 target 的idx
// < 是第一个大于等于 target 的idx
if arr[mid].0 <= target { // 区别在这.
left = mid + 1;
} else {
right = mid;
}
}
}
fn main() {
let arr = [1, 3, 5, 6, 9];
// 右边界查找
if let Some(index) = upper_bound_rightmost_less_than(&arr, 6) {
println!("最后一个 < 6 的下标是：{}，值为 {}", index, arr[index]); // 输出 2, 值为 5
} else {
println!("没有小于 6 的元素");
}
// 左边界查找
if let Some(index) = lower_bound_first_ge(&arr, 5) {
println!("第一个 >= 5 的下标是：{}，值为 {}", index, arr[index]); // 输出 2, 值为 5
} else {
println!("没有大于等于 5 的元素");
}
}
// 标准二分查找（精确匹配）
// 在有序数组中查找恰好等于 target 的元素，如果存在返回下标，否则返回 -1。
fn binary_search_exact(arr: &[i32], target: i32) -> Option<usize> {
let mut left = 0;
let mut right = arr.len() - 1; // 闭区间 [left, right]
while left <= right { // 注意是 <=，因为 right 是闭区间
let mid = left + (right - left) / 2; // 防溢出写法
if arr[mid] == target {
return Some(mid); // 找到目标
} else if arr[mid] < target {
left = mid + 1; // 目标在右侧，排除 mid
} else {
right = mid - 1; // 目标在左侧，排除 mid
}
}
None // 未找到
}
others 随记
fn main() {
let nums = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// 找到第一个大于等于 5 的元素的位置
let idx = nums.partition_point(|&x| x < 5);
println!("{}", idx); // 输出 4（nums[4] = 5）
// 找到第一个大于 5 的元素的位置
let idx = nums.partition_point(|&x| x <= 5);
println!("{}", idx); // 输出 5（nums[5] = 6）
}