2022-07-29：一共有n个人，从左到右排列，依次编号0~n-1，
hi是第i个人的身高，
vi是第i个人的分数，
要求从左到右选出一个子序列，在这个子序列中的人，从左到右身高是不下降的。
返回所有符合要求的子序列中，分数最大累加和是多大。
n <= 10的5次方, 1 <= hi <= 10的9次方, 1 <= vi <= 10的9次方。
来自字节。
答案2022-07-29：
线段树。
代码用rust编写。代码如下：
代码语言：rust复制use rand::Rng;
fn main() {
let nn: i32 = 30;
let vv: i32 = 100;
let test_time: i32 = 20000;
println!("测试开始");
for _ in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) 1;
let mut h = random_array(n, vv);
let mut v = random_array(n, vv);
if right(&mut h, &mut v) != max_sum(&mut h, &mut v) {
println!("出错了!");
break;
}
}
println!("测试结束");
}
// 为了测试
// 绝对正确的暴力方法
fn right(h: &mut Vec<i32>, v: &mut Vec<i32>) -> i32 {
return process(h, v, 0, 0);
}
fn process(h: &mut Vec<i32>, v: &mut Vec<i32>, index: i32, pre_value: i32) -> i32 {
if index == h.len() as i32 {
return 0;
}
let p1 = process(h, v, index 1, pre_value);
let p2 = if h[index as usize] >= pre_value {
v[index as usize] process(h, v, index 1, h[index as usize])
} else {
0
};
return get_max(p1, p2);
}
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 正式方法
// 时间复杂度O(N * logN)
fn max_sum(h: &mut Vec<i32>, v: &mut Vec<i32>) -> i32 {
let n = h.len() as i32;
let mut rank0 = h.clone();
rank0.sort();
let mut st = SegmentTree::new(n);
for i in 0..n {
let height = rank(&mut rank0, h[i as usize]);
// 1~height max
let t = st.max1(height);
st.update1(height, t v[i as usize]);
}
return st.max1(n);
}
// [150, 152, 160, 175] 160
// 1 2 3 4
// 3
fn rank(rank0: &mut Vec<i32>, num: i32) -> i32 {
let mut l = 0;
let mut r = rank0.len() as i32 - 1;
let mut m = 0;
let mut ans = 0;
while l <= r {
m = (l r) / 2;
if rank0[m as usize] >= num {
ans = m;
r = m - 1;
} else {
l = m 1;
}
}
return ans 1;
}
pub struct SegmentTree {
pub n: i32,
pub max: Vec<i32>,
pub update: Vec<i32>,
}
impl SegmentTree {
pub fn new(max_size: i32) -> Self {
let n = max_size 1;
let mut max: Vec<i32> = vec![];
let mut update: Vec<i32> = vec![];
for _ in 0..n << 2 {
max.push(0);
update.push(-1);
}
Self { n, max, update }
}
pub fn update1(&mut self, index: i32, c: i32) {
self.update0(index, index, c, 1, self.n, 1);
}
pub fn max1(&mut self, right: i32) -> i32 {
return self.max0(1, right, 1, self.n, 1);
}
fn push_up(&mut self, rt: i32) {
self.max[rt as usize] = get_max(
self.max[(rt << 1) as usize],
self.max[(rt << 1 | 1) as usize],
);
}
fn push_down(&mut self, rt: i32, _ln: i32, _rn: i32) {
if self.update[rt as usize] != -1 {
self.update[(rt << 1) as usize] = self.update[rt as usize];
self.max[(rt << 1) as usize] = self.update[rt as usize];
self.update[(rt << 1 | 1) as usize] = self.update[rt as usize];
self.max[(rt << 1 | 1) as usize] = self.update[rt as usize];
self.update[rt as usize] = -1;
}
}
fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {
if ll <= l && r <= rr {
self.max[rt as usize] = cc;
self.update[rt as usize] = cc;
return;
}
let mid = (l r) >> 1;
self.push_down(rt, mid - l 1, r - mid);
if ll <= mid {
self.update0(ll, rr, cc, l, mid, rt << 1);
}
if rr > mid {
self.update0(ll, rr, cc, mid 1, r, rt << 1 | 1);
}
self.push_up(rt);
}
fn max0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {
if ll <= l && r <= rr {
return self.max[rt as usize];
}
let mid = (l r) >> 1;
self.push_down(rt, mid - l 1, r - mid);
let mut ans = 0;
if ll <= mid {
ans = get_max(ans, self.max0(ll, rr, l, mid, rt << 1));
}
if rr > mid {
ans = get_max(ans, self.max0(ll, rr, mid 1, r, rt << 1 | 1));
}
return ans;
}
}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..n {
ans.push(rand::thread_rng().gen_range(0, v) 1);
}
return ans;
}执行结果如下：
在这里插入图片描述左神java代码
